Rate this post
Thuật toán này duy trì một tập hợp các đỉnh có đường đi ngắn nhất từ nguồn đã được biết trước. Biểu đồ được biểu diễn bằng ma trận kề chi phí của nó, trong đó chi phí là trọng số của cạnh. Trong ma trận kề chi phí của biểu đồ, tất cả các giá trị đường chéo đều bằng không. Nếu không có đường dẫn nào từ đỉnh nguồn đến bất kỳ đỉnh nào khác Vi thì nó được biểu diễn bằng + ∞ Trong thuật toán này, chúng ta đã giả sử tất cả các trọng số đều dương.
Các bài viết liên quan:
- Ban đầu, không có đỉnh trong tập hợp.
- Đưa đỉnh nguồn Vs vào S. Xác định tất cả các đường đi từ Vs đến tất cả các đỉnh khác mà không đi qua bất kỳ đỉnh nào khác.
- Bây giờ, đưa đỉnh đó vào S gần với Vs nhất và tìm đường đi ngắn nhất đến tất cả các đỉnh qua đỉnh này và cập nhật các giá trị.
- Lặp lại bước cho đến khi n-1 đỉnh không được bao gồm trong S nếu có n đỉnh trong đồ thị.
Sau khi hoàn thành quá trình, chúng tôi nhận được đường đi ngắn nhất đến tất cả các đỉnh từ đỉnh nguồn.
Ví dụ: Tìm đường đi ngắn nhất giữa K và L trong biểu đồ được chỉ ra trong hình bằng cách sử dụng Thuật toán Dijkstra.
Phương pháp:
Bước 1: Đưa đỉnh K là S và xác định tất cả các đường đi trực tiếp từ K đến tất cả các đỉnh khác mà không đi qua đỉnh nào khác.
Khoảng cách đến tất cả các đỉnh khác
Bước 2: Đưa đỉnh trong S gần K nhất và xác định đường đi ngắn nhất đến tất cả các đỉnh qua đỉnh này và cập nhật các giá trị. Đỉnh gần nhất là c.
Khoảng cách đến tất cả các đỉnh khác
Bước 3: Đỉnh thứ 2 gần K nhất là 9, nằm trong S.
Khoảng cách đến tất cả các đỉnh khác
Bước 4: Đỉnh gần thứ 3 với K là b, nằm trong S.
Khoảng cách đến tất cả các đỉnh khác
Bước 5: Đỉnh gần nhất với K là d, nằm trong S.
Vì n-1 đỉnh thuộc S. Do đó ta tìm được khoảng cách ngắn nhất từ K đến tất cả các đỉnh khác. Như vậy, khoảng cách ngắn nhất giữa K và L là 8 và đường đi ngắn nhất là K, c, b, L.
