Tài liệu tham khảo giáo trình Đồ thị và các thuật toán - Chương 3 Các bài toán về đường đi | Chương 3 Các bài toán về dường đi Trong các ứng dung thực tế ta can tìm đường di nếu có giữa hai dính của dế thi. Dặc biệt bài toan tìm dường di ngắn nhất giữa hai dỉnh của mết dó thi có ý nghĩa to lớn. Có thế dan vấ bai toan như vệý từ nhiấu bai toan thực tế. Vó dụ bai toan tìm hanh trình tiết kiệm nhất theo tiếu chuan khoang cóch thoi gian hoặc chi phí trấn một ban đế giao thếng bài toón chon phương phap tiết kiếm nhat dế dưa một hế dếng lụrc tà trang thai . . . nàý sang trang thói khac . Hiện nay co rat nhiấụ phương phap dựa trên lý thuyết đồ thi tỏ ra là cac phương phap có hiệu qua nhốt. Chương nàý trình bàý cac thuật toón tìm dường đi ngắn nhết trên dế thi co trong so. Đường di giữá hái đĩnh Đường đi giữá hái đĩnh Trong nhiếu trường hợp chung ta can tra lời cau h 5i Ton tai đường đi ụ từ đỉnh s đến đỉnh t cua đồ thi cế hướng G V E Nếu cế hay chỉ ra each đi cua đường đi ụ. Lài giai ciỉa bai toón nàý khó dơn gian chung ta chí cến ap dung thuết toan tìm kiếm theo chiếu rếng hoặc chiếu sếu trên dế thi co hướng G như sau. Gan mếi đỉnh ciỉa G mết chỉ sế. Bang phương phap lặp dan đến ta sĩ cho mếi đỉnh V mết chí sế nao đó bằng dế dài dường đi ngắn nhat so cung ót nhót từ s V. Dónh dấụ đỉnh s bang chỉ so 0. Nou cac đỉnh dược đanh dấu bang chỉ sế m lạp thành mết tạp hợp P m đã biết thì ta dónh dấụ chí sế m 1 cho moi đỉnh ciia tạp hợp P m 1 Vj chưa dược đanh dấụ I tến tai vi 2 P m với vi Vj 2 E . 75 Thuật toán dừng khi không thể đánh dấu dii . c nữa. Có hai trường hợp xay ra 1. Đỉnh t được dónh đểu chẳng han t 2 P m vói m nào dó thì tá xót cóc đỉnh v1 v2 . sao cho V1 2 P m - 1 V2 2 P m - 2 . vm 2 P 0 . Khi do ụ s vm vm-1 . v1 tg là dường di phíải tìm. 2. Đỉnh t không dược dónh dôu. Trong lru à iiu li p nay ta kôt luận không ton tai dưàng đi tù s đôn t. Theo cóch xôy đựng ciỉa thuật toón dô dang chứng minh rằng Mệnh dề Nếu đồ thi đuợc xác đinh bởi dãy liên tiếp các đĩnh thì thuật toan co thời gian O m . Đề thị liền thong mạnh Nhắ c lai la dô
