Giải thuật tìm kiếm đường đi ngắn nhất
Thuật toán Dijkstra
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger
Dijkstra, 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.
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. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ
thị.
Ví dụ: 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ố t. 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.
Thuật toán
Thuật toán Dijkstra có thể mô tả như sau:
Ta quản lý một tập hợp động S. Ban đầu S={s}.
Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ
nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v.
Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S.
Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho
phù hợp với định nghĩa.
Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm
đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung
vào tập S.
Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính đúng đắn của
thuật toán. Khi chứng minh tính đúng đắn của thuật toán, chúng ta phải dùng đến tính
chất này.
Chứng minh

đen(BLACK).
* Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để chỉ đỉnh đứng
ngay trước đỉnh u trên đường đi ngắn nhất từ s tới u.
Mã
Procedure Dijkstra {
For each v of V do {
d(v)=M
COLOR(v)=WHITE
d(s)=0

InsertHeap(Q,s)
k=1
While Q khác rỗng do {
u=Head(Q)
Push(Q,u)
k=k-1
COLOR(u)=BLACK
For each v of Ajd(u) {
if COLOR(v)=WHITE then {
k=k+1
HeapIndex(v)=k
InsertHeap(Q,v)
COLOR(v)=GRAY
PRE(v)=u
dv=d(u)+w(u,v)
}
if (COLOR(v)=GRAY) and d(v)>d(u)+w(u,v) then{
d(v)=d(u)+w(u,v)
PRE(v)=u
UpHeap(Q,HeapIndex(v))

nối của hai đường đi từ u tới k rồi từ k tới v (Chú ý rằng ta còn có việc lưu lại vết):
Mã:
for(int k = 0; k < n; k++)
for(int u = 0; u < n; u++)
for(int v = 0; v < n; v++)
c[u,v] = min(c[u,v], c[u,k] + c[k,v]);
Tính đúng của thuật toán:
Gọi c(k)[u,v] là độ dài đường đi ngắn nhất từ u tới v mà chỉ đi qua các đỉnh trung gian
thuộc tập {1,2, ,k}. Rõ ràng k = 0 thì c(0)[u,v] = c[u,v] (đường đi ngắn nhất là đường
đi trực tiếp).
Giả sử ta đã tính được các c(k-1)[u,v] thì c(k)[u,v] sẽ được xây dựng như sau:
Nếu đường đi ngắn nhất từ u tới v mà chỉ qua các đỉnh trung gian thuộc tập {1,2, ,k}
lại:
+ Không đi qua đỉnh k thì tức là chỉ qua các đỉnh trung gian thuộc tập {1,2, ,k-1} thì:
Mã:
c(k)[u,v] = c(k-1)[u,v]
+ Có đi qua đỉnh k thì đường đi đó sẽ là nối của một đường đi từ u tới k và một đường
đi từ k tới v, hai đường đi này chỉ đi qua các đỉnh trung gian thuộc tập {1,2, ,k-1}.
Mã:
c(k)[u,v] = c(k-1)[u,k] + c(k-1)[k,v]
Vì ta muốn c(k)[u,v] là cực tiểu nên suy ra: c(k)[u,v] = min(c(k-1)[u,v], c(k-1)[u,k] +
c(k-1)[k,v]).
Và cuối cùng, ta quan tâm tới c(n)[u,v]: độ dài đường đi ngắn nhất từ u tới v mà chỉ đi
qua các đỉnh trung gian thuộc tập {1,2, ,n}.
Khi cài đặt thì ta sẽ không có các khái niệm c(k)[u,v] mà sẽ thao tác trực tiếp trên các
trọng số c[u,v], c[u,v] tại bước tối ưu thứ k sẽ được tính toán để tối ưu qua các giá trị
c[u,v]; c[u,k] và c[k,v] tại bước thứ k-1. Và nếu cài đặt duới dạng ba vòng lặp for lồng
như trên, do có sự tối ưu bắc cầu tại mỗi bước, tốc độ tối ưu c[u,v] chỉ tăng lên chứ
không thể giảm đi được