MỘT SỐ BÀI TOÁN ỨNG DỤNG (Bài toán tìm đường đi ngắn nhất và bài toán luồng cực đại) Bài toán tìm đường đi ngắn nhất Tìm đường đi ngắn nhất trong đồ thị không có trọng số Bài toán: Cho đồ thị không có trọng số G = (V,E) và hai đỉnh u, v ∈ V. | Giáo án môn Lý Thuyết Đô Thị Chương 6 MỘT SỐ BÀI TOÁN ỨNG DỤNG Bài toán tìm đường đi ngắn nhất và bài toán luồng cực đại Bài toán tìm đường đi ngắn nhất Tìm đường đi ngắn nhất trong đồ thị không có trọng số Bài toán Cho đồ thị không có trọng số G V E và hai đỉnh u v e V. Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v tức là đường đi từ u đến v có số cạnh cung là ít nhất Để giải quyết bài toán này ta có thể thực hiện theo thuật toán sau đây Thuât toán Bước 1 Tại đỉnh u ta ghi số 0 Các đỉnh kề với u có cạnh đi từ u đến ta ghi số 1 Các đỉnh kề với các đỉnh đã được ghi số 1 ta ghi số 2 Giả sử ta đã ghi tới i tức là ta đã đánh số được các tập đỉnh là V 0 u V 1 V 2 . V i . Trong đó V i là tập tất cả các đỉnh được ghi bởi số i. Ta xác định tập các đỉnh được đánh số bởi số i 1 như sau V i 1 x x e V xỂ V k với k 0 1 . i và 3 ye V i sao cho từ y có cạnh cung đi tưới x Do tính hữu hạn của đồ thị sau một số hữu hạn bước thuật toán dừng lại và cho ta tập các đỉnh có chứa đỉnh v được đánh số bởi m là V m . Bước 2 Do ở bước 1 đỉnh v được đánh số là m điều này chứng tỏ đường đi từ u đến v có m cạnh cung và là đường đi ngắn nhất từ u tới v. Để tìm tất cả các đường đi có độ dài m ngắn nhất từ u tới v ta xuất phát từ v đi ngược về u theo nguyên tắc sau đây - Tìm tất cả các đỉnh có cạnh cung tới b được ghi số m-1 giả sử đó là xik k 1 2. . - Với mỗi đỉnh xik tìm tất cả các đỉnh có cạnh cung tới xik được ghi số m-2. Bằng cách lùi dần trở lại đến một lúc nào đó gặp đỉnh ghi số 0 đó chính là đỉnh u. Tất cả các đường đi xác đinh theo các bước trên là đường đi từ u tới v với độ dài m ngắn nhất cần tìm Ví dụ Xét đồ thị có hướng cho bởi hình dưới đây Hình Tìm đường đi ngắn nhất từ đỉnh v1 đế 60 Nguyễn Minh Đức - ĐHQG Hà Nội Giáo án môn Lý Thuyết Đô Thị Chu ý Thuật toán tìm đường đi giữa hai đỉnh u và v trong đồ thị bằng cách áp dụng thuật toán tìm kiếm theo chiều rộng chính là đường đi ngắn nhất từ u tới v theo số cạnh . Tìm đường đi ngắn nhất trong đồ thị có trọng số Bài .
