Trong tài liệu này các bạn sẽ được làm rõ thuật toán này qua một số ví dụ để các bạn thực hành, hãy làm nó bạn sẽ hiểu Dijstra là gì, tại sao nó là kinh điển | UNIVERSITY Đường đi ngắn nhất Giới thiệu Bài toán tìm đường đi ngắn nhất là bài toán quan trọng trong lý thuyết đồ thi. Được ứng dụng trong thực tế Giao thông viễn thông. Bài toán chia làm 2 loại Tìm đường đi ngắn nhất giữa 1 cặp đỉnh Cho 2 đỉnh u v thuộc G tìm đường đi ngắn nhất từ u đến v Dịkstra Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v với mọi cặp đỉnh u v thuộc G Floyd-Warshall UNI RSITY Giải thuật Dijkstra Giới thiệu - Giải thuật Dijkstra giải bài toán đường đi ngắn nhất nguồn đơn Single Source Shortest Path trên một đồ thị có trọng số cạnh đều không âm. - Xác định đường đi ngắn nhất giữa 2 đỉnh a b cho trước Đặt vấn đề Ứng dụng giải thuật cây bao trùm tối thiểu để giải quyết bài toán đường di ngắn nhất có được không A 2 B F Cc 1 1 E - - D w 1 UNIVERSITY Giải thuật Dịkstra Nhận xét - Giải thuật để giải bài toán MST sẽ không ứng dụng được cho bài toán đường đi ngắn nhất. - Vì sao - Vì vậy cần phải chỉnh sửa giải thuật trên để phù hợp với bài toán đường đi ngắn .
