Giới thiệu: Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956 và ấn bản năm 1959, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm[1].
Bài toán:
Cho một đồ thị có hướng G = (V, E), một hàm trọng số w: E = [0; +∞) và một đỉnh nguồn s, đỉnh đích f. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh đích f.
Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố f. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi.
Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ, với 3 đỉnh A, B, C đường đi A→B→C có thể ngắn hơn so với đường đi trực tiếp A→C.
Bộ dữ liệu:
Dữ liệu vào chứa các số n, m, s, f tương ứng với số đỉnh, số cạnh, đỉnh nguồn, đỉnh đích. m dòng tiếp theo chứa 3 số u, v, k với ý nghĩa là đường đi từ đỉnh u đến đỉnh v là k.
Dữ liệu ra là dãy các đỉnh là đường đi ngắn nhất từ đỉnh s đến đỉnh f.
Đây là một ví dụ:
 |
| Đồ thị ban đầu |
 |
| Đường đi ngắn nhất là 1→5→6 với độ dài 25 |
Khai báo:
Mảng fr kiểu boolean để đánh dấu những đỉnh sẽ xét. fr[i] = True là đỉnh i chưa được xét.
Mảng d kiểu số nguyên chứa đường đi ngắn nhất hiện thời.
Mảng trace kiểu số nguyên lưu lại các đỉnh để sau này truy vết tìm đường đi ngắn nhất.
Khởi tạo:
Hai đỉnh không có đường đi được quy ước có độ dài là +∞; hai đỉnh trùng nhau có độ dài bằng không, có nghĩa là a[i, i] = 0.
d[s] được gán bằng 0, các đỉnh còn lại được gán là +∞.
Thiết kế:
Lặp mãi 3 câu lệnh 1, 2, 3 này cho đến khi có lệnh thoát:
1. Tìm đỉnh u = [1; n] mà d[u] là nhỏ nhất và u chưa bị đánh dấu.
2. Nếu u = 0 (không tìm thấy) hoặc u = f (đã tìm được đường đi ngắn nhất đến f) thì thoát vòng lặp.
3. Đánh dấu đỉnh u lại. Tìm đỉnh v = [1; n] mà a[u, v] > 0 (kề), d[v] > d[u] + a[u, v] (đường đi từ s→u + u→v có độ dài nhỏ hơn đường đi từ s→v) và v chưa được đánh dấu thì cập nhật: d[v] := d[u] + a[u, v], đồng thời gán trace[v] := u (v được đến từ u).
4. Truy vết tìm đường đi.
Chương trình:Xem tại đây: http://mivi.pro/CANIW
[1]: https://vi.wikipedia.org/wiki/Thuật_toán_Dijkstra
