TAILIEUCHUNG - Bài giảng Toán rời rạc: Đường đi trên đồ thị (Version 0.2) - Trần Vĩnh Đức

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 .

• Toán học
• Bài giảng Toán rời rạc
• Toán rời rạc
• Đường đi trên đồ thị
• Tìm kiếm theo chiều rộng
• Thuật toán Dijkstra
• Cài đặt hàng đợi ưu tiên
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi Toán rời rạc
• Bài tập Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• Bài giảng môn học Toán học rời rạc
• Toán học rời rạc
• Môn Toán học rời rạc
• Tập hợp và logic mệnh đề
• lý thuyết toán rời rạc
• đề cương Toán rời rạc