tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 3 - Nguyễn Thanh Sơn

Chương 3 - Các bài toán đường đi. Những nội dung chính được trình bày trong chương này gồm có: Đườ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ị Euler; đồ thị Hamilton. . | CÁC BÀI TOÁN ĐƯỜNG ĐI ntsonptnk@ 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 ĐƯỜNG ĐI NGẮN NHẤT Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn C B A E D F 0 3 2 8 5 8 4 8 7 1 2 5 2 3 9 Cho đồ thị có hướng có trọng G=(X, E) và hai đỉnh s, 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 định nghĩa là: L(P) = (e P)L(e) Bài toán: tìm đường đi từ s đến t có trọng lượng nhỏ nhất BÀI TOÁN Lý thuyết đồ thị - Nguyễn Thanh Sơn 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 . | CÁC BÀI TOÁN ĐƯỜNG ĐI ntsonptnk@ 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 ĐƯỜNG ĐI NGẮN NHẤT Lý thuyết đồ thị - chương 3 - Nguyễn Thanh Sơn C B A E D F 0 3 2 8 5 8 4 8 7 1 2 5 2 3 9 Cho đồ thị có hướng có trọng G=(X, E) và hai đỉnh s, 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 định nghĩa là: L(P) = (e P)L(e) Bài toán: tìm đường đi từ s đến t có trọng lượng nhỏ nhất BÀI TOÁN Lý thuyết đồ thị - Nguyễn Thanh Sơn 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. NHẬN XÉT Lý thuyết đồ thị - Nguyễn Thanh Sơn P là một đường đi từ s đến t, giả sử P có chứa một mạ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( ) Lý thuyết đồ thị - Nguyễn Thanh Sơn s t k 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. DỮ LIỆU NHẬP Lý thuyết đồ thị - Nguyễn Thanh Sơn C A B D 12 7 15 5 16 14 NGUYÊN LÝ BELLMAN Lý thuyết đồ thị - Nguyễn .