Chương 3 - CÁC BÀI TOÁN ĐƯỜNG ĐI

Bài toán được phát biểu cho đồ thị có hướng có trọng, nhưng các thuật toán sẽ trình bày đều có thể áp dụng cho các đồ thị vô hướng có trọng bằng cách xem mỗi cạnh của đồ thị vô hướng như hai cạnh có cùng trọng lượng nối cùng một cặp đỉnh nhưng có chiều ngược nhau.Khi tìm đường đi ngắn nhất có thể bỏ bớt đi các cạnh song song và chỉ chừa lại một cạnh có trọng lượng nhỏ nhất.Đối với các khuyên có trọng lượng không âm thì cũng có thể bỏ đi mà không...
Nội dung trích xuất từ tài liệu:
Chương 3 - CÁC BÀI TOÁN ĐƯỜNG ĐICÁC BÀI TOÁN ĐƯỜNG ĐI ntsonptnk@gmail.com NỘI DUNGĐường đi ngắn nhất Bài toán Nguyên lý Bellman Thuật toán Dijkstra Thuật toán Floyd Thuật toán Ford-BellmanĐồ thị EulerĐồ thị Hamilton Lý thuyết đồ thị , chương 3 - Nguyễn Thanh Sơn 2 0 A 4 8 2 8 2 3 7 1 B C D 3 9 5 8 2 5 E FĐƯỜNG ĐI NGẮN NHẤT Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 3 BÀI TOÁNCho đồ thị có hướng có trọng G=(X, E) và hai đỉnhs, t ∈X, gọi P là một đường đi từ đỉnh s đến đỉnh t,trọng lượng (hay giá) của đường đi P được địnhnghĩa là: L(P) = ∑(e∈P)L(e)Bài toán: tìm đường đi từ s đến t có trọng lượngnhỏ nhất Lý thuyết đồ thị - Nguyễn Thanh Sơn 4 NHẬN XÉT Bài toán được phát biểu cho đồ thị có hướng có trọng, nhưng các thuật toán sẽ trình bày đều có th ể áp d ụng cho các đồ thị vô hướng có trọng bằng cách xem mỗi cạnh của đồ thị vô hướng như hai cạnh có cùng trọng lượng nối cùng một cặp đỉnh nhưng có chiều ngược nhau. Khi tìm đường đi ngắn nhất có thể bỏ bớt đi các cạnh song song và chỉ chừa lại một cạnh có trọng lượng nh ỏ nhất. Đối với các khuyên có trọng lượng không âm thì cũng có thể bỏ đi mà không làm ảnh hưởng đến kết quả của bài toán. Đối với các khuyên có trọng lượng âm thì có thể đưa đến bài toán đường đi ngắn nhất không có lời giải . Lý thuyết đồ thị - Nguyễn Thanh Sơn 5 ĐIỀU KIỆN TỒN TẠI LỜI GiẢIP là một đường đi từ s đến t, giả sử P có chứa mộtmạch µ. Nếu L(µ) ≥ 0 thì có thể cải tiến đường đi P bằng cách bỏ đi mạch µ. Nếu L(µ) < 0 thì không tồn tại đường đi ngắn nhất từ đỉnh s đến đỉnh t vì nếu quay vòng tại µ càng nhiều vòng thì trọng lượng đường đi P càng nhỏ đi, tức là L(P)→ -∞ . k t s µ Lý thuyết đồ thị - Nguyễn Thanh Sơn 6 DỮ LIỆU NHẬPMa trận trọng lượng LNxN được định nghĩa: Lij = trọng lượng cạnh nhỏ nhất nối i đến j nếu có, Lij = ∞ nếu không có cạnh nối i đến j.Khi cài đặt thuật toán có thể dùng 0 thay cho ∞ bằng cách đưa thêm một số kiểm tra thích hợp. 12  0 12 7 ∞  B A    ∞ 0 15 14  16 7 ∞ ∞ 0 ∞  5 15 14   5 ∞ ∞ 0   D C Lý thuyết đồ thị - Nguyễn Thanh Sơn 7 k P1 P2 ts P1’NGUYÊN LÝ BELLMAN Lý thuyết đồ thị - Nguyễn Thanh Sơn 8 NGUYÊN LÝ BELLMANGọi P là đường đi ngắn nhất từ đỉnh s đến đỉnh t; k ∈ P. Giả sử P=P1⊕P2 với P1 là đường đi con của P từ s đến k và P2 là đường đi con của P từ k đến t. Khi đó P1 cũng là đường đi ngắn nhất từ s đến k. k P1 P2 t s P1’ L(P1’) < L(P1) ⇒ L(P1’⊕ P2) < L(P1⊕ P2)=L(P) Lý thuyết đồ thị - Nguyễn Thanh Sơn 9 0 A 4 8 2 8 2 3 7 1 B C D 3 9 5 8 2 5 E FTÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ CÓ TRỌNG SỐ DƯƠNG THUẬT TOÁN DIJKSTRA Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn 10 THUẬT TOÁN DI ...