Định nghĩa
Thuật toán Dijkstra tìm đường đi ngắn nhất từ một nút cụ thể, được gọi là nút nguồn đến mọi nút khác trong một biểu đồ được kết nối. Nó tạo ra một cây đường dẫn ngắn nhất với nút nguồn là gốc. Nó được sử dụng sâu rộng trong mạng máy tính để tạo ra các tuyến đường tối ưu với mục đích giảm thiểu chi phí định tuyến.
Thuật toán Dijkstra
Đầu vào - Một đồ thị đại diện cho mạng; và một nút nguồn, s
Đầu ra - Cây đường dẫn ngắn nhất, spt [], với s là nút gốc.
Khởi tạo -
-
Một mảng khoảng cách dist [] có kích thước | V | (số nút), trong đó dist [s] = 0 và dist [u] =∞ (vô hạn), trong đó u đại diện cho một nút trong biểu đồ ngoại trừ s.
-
Một mảng, Q , chứa tất cả các nút trong biểu đồ. Khi thuật toán chạy xong, Q sẽ trở nên trống rỗng.
-
Tập hợp trống, S , mà các nút đã truy cập sẽ được thêm vào. Khi thuật toán chạy xong, S sẽ chứa tất cả các nút trong biểu đồ.
-
Lặp lại trong khi Q không trống -
-
Xóa khỏi Q , nút, u có dist [u] nhỏ nhất và không có trong S. Trong lần chạy đầu tiên, dist [s] bị xóa.
-
Thêm u vào S, đánh dấu u là đã ghé thăm.
-
Đối với mỗi nút v liền kề với u, hãy cập nhật dist [v] thành -
-
Nếu ( dist [u] + trọng lượng của cạnh u-v )
Sau đó -
Cập nhật dist [v] =dist [u] + trọng lượng của cạnh u-v
-
-
-
-
Mảng dist [] chứa đường dẫn ngắn nhất từ s đến mọi nút khác.
Ví dụ
Hoạt động của thuật toán có thể được hiểu rõ nhất bằng cách sử dụng một ví dụ. Hãy xem biểu đồ sau có các nút được đánh dấu từ A đến G, được nối với nhau bằng các cạnh có trọng số như sau -
Quá trình khởi tạo sẽ như sau -
-
dist [7] ={0, ∞, ∞, ∞, ∞, ∞, ∞}
-
Q ={A, B, C, D, E, F, G}
-
S𝑆 =∅
Vượt qua 1 - Chúng tôi chọn nút A từ Q vì nó có dist [] thấp nhất giá trị của 0 và đặt nó trong S. Các nút lân cận của A là B và C. Chúng tôi cập nhật các giá trị dist [] tương ứng với B và C theo thuật toán. Vì vậy, các giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6, ∞, ∞, ∞, ∞}
-
Q ={B, C, D, E, F, G}
-
S ={A}
Khoảng cách và đường đi ngắn nhất sau khi vượt qua này được thể hiện trong biểu đồ sau. Nút màu xanh lục biểu thị nút đã được thêm vào S -
Vượt qua 2 - Chúng tôi chọn nút B từ Q vì nó có dist [] thấp nhất giá trị của 5 và đặt nó vào S. Các nút lân cận của B là C, D và E . Chúng tôi cập nhật các giá trị dist [] tương ứng với C, D và E theo thuật toán. Vì vậy, các giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6,12,13, ∞, ∞}
-
Q ={C, D, E, F, G}
-
S ={A, B}
Khoảng cách và con đường ngắn nhất sau khi vượt qua này là -
Vượt qua 3 - Chúng tôi chọn nút C từ Q vì nó có giá trị dist [] thấp nhất là 6 và đặt nó vào S. Các nút lân cận của C là D và F. Chúng tôi cập nhật các giá trị dist [] tương ứng với D và F. Vì vậy, giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6,8,13,10, ∞}
-
Q ={D, E, F, G}
-
S ={A, B, C}
Khoảng cách và con đường ngắn nhất sau khi vượt qua này là -
Vượt qua 4 - Chúng tôi chọn nút D từ Q vì nó có dist [ thấp nhất ] giá trị của 8 và đặt nó trong S. Các nút lân cận của D là E, F và G. Chúng tôi cập nhật dist [] giá trị tương ứng với E, F và G . Vì vậy, các giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6,8,10,10,18}
-
Q ={E, F, G}
-
S ={A, B, C, D}
Khoảng cách và con đường ngắn nhất sau khi vượt qua này là -
Vượt qua 5 - Chúng ta có thể chọn nút E hoặc nút F từ Q vì cả hai đều có dist [] thấp nhất giá trị của 10 . Chúng tôi chọn bất kỳ một trong số chúng, nói E và đặt nó vào S . Các nút lân cận của D là G . Chúng tôi cập nhật dist [] các giá trị tương ứng với G. Vì vậy, các giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6,8,10,10,13}
-
Q ={F, G}
-
S ={A, B, C, D, E}
Khoảng cách và con đường ngắn nhất sau khi vượt qua này là -
Vượt qua 6 - Chúng tôi chọn nút F từ Q vì nó có dist [] thấp nhất giá trị của 10 và đặt nó vào S . Các nút lân cận của F là G . dist [] giá trị tương ứng với G nhỏ hơn giá trị đó đến F . Vì vậy, nó vẫn như cũ. Các giá trị của cấu trúc dữ liệu trở thành -
-
dist [7] ={0,5,6,8,10,10,13}
-
Q ={G}
-
S ={A, B, C, D, E, F}
Khoảng cách và con đường ngắn nhất sau khi vượt qua này là -
Vượt qua 7 - Chỉ có một nút trong Q . Chúng tôi xóa nó khỏi Q đặt nó trong S. Mảng dist [] không cần thay đổi. Bây giờ, Q trở nên trống rỗng, S chứa tất cả các nút và vì vậy chúng ta đi đến phần cuối của thuật toán. Chúng tôi loại bỏ tất cả các cạnh hoặc các tuyến không nằm trong đường đi của bất kỳ tuyến nào. Vì vậy, cây đường dẫn ngắn nhất từ nút nguồn A đến tất cả các nút khác như sau -