tailieunhanh - Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths
Nội dung "Bài giảng Phân tích thiết kế giải thuật - Chương 10: Single-Source Shortest Paths" tập trung vào những kiến thức cơ bản nhất về những cách giải bài toán các đường đi ngắn nhất từ một đỉnh nguồn, biểu diễn các đường đi ngắn nhất. Mời các bạn tham khảo. | Single-Source Shortest Paths Các đường đi ngắn nhất từ một đỉnh nguồn Bài toán các đường đi ngắn nhất: một số thuật ngữ. Cho một đồ thị có trọng số, có hướng G = (V, E), với một hàm trọng số w : E Trọng số của một đường đi p = v0 , v1, , vk w(p) = i = 1 k w(vi 1 , vi ) Trọng số của đường đi ngắn nhất (shortest path weight) từ u đến v min{w(p) : u v } nếu có đường đi từ u đến v các trường hợp khác Đường đi ngắn nhất từ u đến v là bất kỳ đường đi p nào từ u đến v sao cho w(p) = d(u, v). d(u, v) = p 3 6 7 2 4 3 6 2 5 1 t v x y u Ch. 10: Single-Source Shortest Paths Các đường đi ngắn nhất từ một đỉnh nguồn (tiếp) Bài toán các đường đi ngắn nhất từ một nguồn duy nhất (Single-source shortest-paths problem): Cho đồ thị G = (V, E) và một đỉnh nguồn s V. Tìm đường đi ngắn nhất từ s đến mọi đỉnh v V. 3 6 7 2 4 3 6 2 5 1 s Ch. 10: Single-Source Shortest Paths Cạnh có trọng số âm Giả thiết: Trọng số của cạnh có thể âm Chu trình có thể có trọng số âm Nếu tồn tại một chu trình có trọng số âm đến được (reachable) từ s thì trọng số của đường đi ngắn nhất không được định nghĩa: không đường đi nào từ s đến một đỉnh nằm trên chu trình có thể là đường đi ngắn nhất. 3 1 4 a b 5 11 6 c d 3 e f 0 3 6 4 8 7 3 5 2 s g 2 8 3 i h j số trong mỗi đỉnh là trọng số đường đi ngắn nhất từ đỉnh nguồn s. Ch. 10: Single-Source Shortest Paths Cạnh có trọng số âm (tiếp) Nếu tồn tại một chu trình có trọng số âm trên một đường đi từ s đến v, ta định nghĩa d(s, v) = . Trong ví dụ sau, các đỉnh h, i, j không đến được từ s nên có trọng số đường đi ngắn nhất là (chứ không là mặc dù chúng nằm trên một chu trình có trọng số âm). 3 1 4 a b 5 11 6 c d 3 e f 0 3 6 4 8 7 3 5 2 s g 2 8 3 i h j Ch. 10: Single-Source Shortest Paths Biểu diễn các đường đi ngắn nhất Đồ thị G = (V, E ) Với mọi đỉnh v, đỉnh cha (predecessor) của v là một đỉnh khác hay là NIL. Duy trì p[v], con trỏ đến | Single-Source Shortest Paths Các đường đi ngắn nhất từ một đỉnh nguồn Bài toán các đường đi ngắn nhất: một số thuật ngữ. Cho một đồ thị có trọng số, có hướng G = (V, E), với một hàm trọng số w : E Trọng số của một đường đi p = v0 , v1, , vk w(p) = i = 1 k w(vi 1 , vi ) Trọng số của đường đi ngắn nhất (shortest path weight) từ u đến v min{w(p) : u v } nếu có đường đi từ u đến v các trường hợp khác Đường đi ngắn nhất từ u đến v là bất kỳ đường đi p nào từ u đến v sao cho w(p) = d(u, v). d(u, v) = p 3 6 7 2 4 3 6 2 5 1 t v x y u Ch. 10: Single-Source Shortest Paths Các đường đi ngắn nhất từ một đỉnh nguồn (tiếp) Bài toán các đường đi ngắn nhất từ một nguồn duy nhất (Single-source shortest-paths problem): Cho đồ thị G = (V, E) và một đỉnh nguồn s V. Tìm đường đi ngắn nhất từ s đến mọi đỉnh v V. 3 6 7 2 4 3 6 2 5 1 s Ch. 10: Single-Source Shortest Paths Cạnh có trọng số âm Giả thiết: Trọng số của cạnh có thể âm Chu trình có thể có
đang nạp các trang xem trước
