Chương 5 trang bị cho người học những kiến thức cơ bản về bài toán đường đi ngắn nhất. Thông qua chương này người học có thể hiểu được: Bài toán đường đi ngắn nhất (ĐĐNN); tính chất của ĐĐNN, giảm cận trên; thuật toán Bellman-Ford; thuật toán Dijkstra; đường đi ngắn nhất trong đồ thị không có chu trình; thuật toán Floyd-Warshal. | Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Chương 5 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Nội dung . Bài toán đường đi ngắn nhất (ĐĐNN) . Tính chất của ĐĐNN, Giảm cận trên . Thuật toán Bellman-Ford . Thuật toán Dijkstra . Đường đi ngắn nhất trong đồ thị không có chu trình . Thuật toán Floyd-Warshal Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất . Bài toán đường đi ngắn nhất Cho đơn đồ thị có hướng G = (V,E) với hàm trọng số w: E ® R (w(e) được gọi là độ dài hay trọng số của cạnh e) Độ dài của đường đi P = v1 ® v2 ® ® vk là số Đường đi ngắn nhất từ đỉnh u đến đỉnh v là đường đi có độ dài ngắn nhất trong số các đường đi nối u với v. Độ dài của đường đi ngắn nhất từ u đến v còn được gọi là khoảng cách từ u tới v và ký hiệu là (u,v). Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Ví dụ path s s,a s,a,b s,a,b,c s,a,d s,a,b,e s,a,b,e,f weight 0 3 4 6 6 6 9 s a b c d e f Cho đồ thị có trọng số G = (V, E), và đỉnh nguồn s V, hãy tìm đường đi ngắn nhất từ s đến mỗi đỉnh còn lại. a s b e f d c 3 3 5 1 2 2 2 4 1 6 3 5 đỉnh nguồn Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Các ứng dụng thực tế Giao thông (Transportation) Truyền tin trên mạng (Network routing) (cần hướng các gói tin đến đích trên mạng theo đường nào?) Truyền thông (Telecommunications) Speech interpretation (best interpretation of a spoken sentence) Điều khiển robot (Robot path planning) Medical imaging Giải các bài toán phức tạp hơn trên mạng . Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Các dạng bài toán ĐĐNN Bài toán một nguồn một đích: Cho hai đỉnh s và t, cần tìm đường đi ngắn nhất từ s đến t. Bài toán một nguồn nhiều đích: Cho s là đỉnh nguồn, cần tìm đường đi ngắn nhất từ s đến tất cả các đỉnh còn lại. Bài toán mọi cặp: Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị. Đường đi ngắn nhất theo số cạnh - BFS. Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Nhận xét Các . | Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Chương 5 BÀI TOÁN ĐƯỜNG ĐI NGẮN NHẤT Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Nội dung . Bài toán đường đi ngắn nhất (ĐĐNN) . Tính chất của ĐĐNN, Giảm cận trên . Thuật toán Bellman-Ford . Thuật toán Dijkstra . Đường đi ngắn nhất trong đồ thị không có chu trình . Thuật toán Floyd-Warshal Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất . Bài toán đường đi ngắn nhất Cho đơn đồ thị có hướng G = (V,E) với hàm trọng số w: E ® R (w(e) được gọi là độ dài hay trọng số của cạnh e) Độ dài của đường đi P = v1 ® v2 ® ® vk là số Đường đi ngắn nhất từ đỉnh u đến đỉnh v là đường đi có độ dài ngắn nhất trong số các đường đi nối u với v. Độ dài của đường đi ngắn nhất từ u đến v còn được gọi là khoảng cách từ u tới v và ký hiệu là (u,v). Toán rời rạc, Fall 2005 Bài toán đường đi ngắn nhất Ví dụ path s s,a s,a,b s,a,b,c s,a,d s,a,b,e s,a,b,e,f weight 0 3 4 6 6 6 9 s a b c d e f Cho đồ thị có trọng .
