tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 7 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 7 Bài toán tìm đường đi ngắn nhất, được biên soạn gồm các nội dung chính sau: Thuật toán Ford-Bellman; Thuật toán Dijkstra; Thuật toán Floyd. Mời các bạn cùng tham khảo! | Chương 7 Bài toán tìm đường đi ngắn nhất Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 Bài toán tìm đường đi ngắn nhất 2 Lý thuyết đồ thị I. Giới thiệu Xét đồ thị có hướng có trọng số G V E if u v E TrongSo u v a u v if u v E Với a u v R Nếu dãy v0 v1 vp là 1 đường đi trên G thì độ dài của nó được định nghĩa p DoDai v0 v1 . v p a vi 1 vi i 1 Chương 7 Bài toán tìm đường đi ngắn nhất 3 I. Giới thiệu Bài toán đường đi ngắn nhất Giả sử có nhiều đường đi từ v0 đến vp Đường đi ngắn nhất là đường đi có tổng trọng số các cung nhỏ nhất. Đường đi từ một đỉnh Ford-Bellman Dijkstra Đường đi từ một đỉnh Floyd Chương 7 Bài toán tìm đường đi ngắn nhất 4 Nội dung I. Giới thiệu II. Thuật toán Ford-Bellman III. Thuật toán Dijkstra IV. Thuật toán Floyd Chương 7 Bài toán tìm đường đi ngắn nhất 5 Lý thuyết đồ thị II. Thuật toán Ford-Bellman Thuật toán Ford-Bellman dùng để tìm đường đi ngắn nhất từ một đỉnh s đến tất cả các đỉnh còn lại của đồ thị. Được sử dụng cho đồ thị không có chu trình âm. Cho đồ thị có hướng có trọng số G V E . Trọng số của các cạnh của G được tính như sau TrongSo u v nếu cung u v E. TrongSo u v a u v nếu cung u v E. Thuật toán tìm đường đi ngắn nhất d v từ đỉnh s đỉnh v mọi v V Xét u V. Nếu d u TrongSo u v lt d v thì ta thay d v d u TrongSo u v . Quá trình này sẽ được lặp lại cho đến khi không thể có giá trị d v tốt hơn. Chương 7 Bài toán tìm đường đi ngắn nhất 6 II. Thuật toán Ford-Bellman Cài đặt thuật toán Đầu vào Đồ thị có hướng G V E với n đỉnh. s V là đỉnh xuất phát. a u v u v V là ma trận trọng số Đầu ra Khoảng cách từ s đến tất cả các đỉnh còn lại d v v V. Truoc v v V là đỉnh đi trước v trong đường đi ngắn nhất từ s đến v Chương 7 Bài toán tìm đường đi ngắn nhất 7 II. Thuật toán Ford-Bellman void Ford_Bellman for v V Khởi tạo d và Truoc d v a s v Truoc v s d s 0 for k 1 k lt n-1 k for v V s for u V if d v gt d u a u v d v d u a u v Truoc v u Độ phức tạp của thuật toán là O n3 Chương 7 Bài toán .