Bài giảng Toán rời rạc: Đường đi trên đồ thị (Version ) cung cấp cho người học những nội dung kiến thức như: Khoảng cách và tìm kiếm theo chiều rộng, thuật toán Dijkstra, cài đặt hàng đợi ưu tiên, đường đi ngắn nhất khi có cạnh độ dài âm, đường đi ngắn nhất trong một DAG. Mời các bạn cùng tham khảo. | Đường đi trên đồ thị Version Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 https tailieudientucntt 1 52 Tài liệu tham khảo S. Dasgupta C. H. Papadimitriou and U. V. Vazirani Algorithms July 18 2016. Chú ý Nhiều hình vẽ trong tài liệu được lấy tùy tiện mà chưa xin phép. https tailieudientucntt 2 52 Nội dung Khoảng cách và tìm kiếm theo chiều rộng Thuật toán Dijkstra Cài đặt hàng đợi ưu tiên Đường đi ngắn nhất khi có cạnh độ dài âm Đường đi ngắn nhất trong một DAG https tailieudientucntt In Figure for example vertex B is at distance 2 from S and there are two shorte DFStovàit. đường paths When S is điheld up the strings along each of these paths become ta aph and b its depth-first search tree. Figure a A simple graph and b its depth-first search tree. b S a b S A E S A A D A D B E B E B D C B C C 104 Đường đi trên cây DFS thường không phải là đường đi ngắn nhất. https tailieudientucntt 4 52 vertex s high enough the other balls that get pulled up along with it are precisely theKhoảng cách from s. And to find their distances from s you need only vertices reachable measure how far below s they hang. In Figure for example vertex B is at distance 2 from S and there are two shortest paths to it. When S is held up the strings along each of these paths become taut. Khoảng cách giữa hai đỉnh là độ dài của đường đi ngắn nhất giữa Figure a A simple graph and b its depth-first search tree. chúng. a b v Khoảng cách S v S E S A A A D B C B E D C B D E C 104 https tailieudientucntt 5 52 Mô hình vật lý của đồ thị Algorithms 105 Algorithm Giả sử rằng mọi cạnh có cùng độ dài. Ta nhấc đỉnh S lên A physical model Figure of a graph. A physical model of a graph. S S S E A S A A C D EA C D E C D B C B B B On the other hand edge D E plays no role in any shortest path and the hand edgeslack. remains D E plays no role in any .
