Trường hợp ma trận số không âm. Thuật toán dijkstra
Trong trường hợp trọng số trên các cung là không âm thuật toán do Dijkstra đề nghị làm việc hữu hiệu hơn rất nhiều so với thuật toán trình bày trong mục trước. Thuật toán được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn ...
Trong trường hợp trọng số trên các cung là không âm thuật toán do Dijkstra đề nghị làm việc hữu hiệu hơn rất nhiều so với thuật toán trình bày trong mục trước. Thuật toán được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của mỗi đỉnh cho biết cận của độ dài đường đi ngắn nhất từ s đến nó. Các nhãn này sẽ được biến đổi theo một thủ tục lặp, mà ở mỗi bước lặp có một nhãn tạm thời trở thành nhãn cố định. Nếu nhãn của một đỉnh nào đó trở thành một nhãn cố định thì nó sẽ cho ta không phải là cận trên mà là độ dài của đường đi ngắn nhất từ đỉnh s đến nó. Thuật toán được mô tả cụ thể như sau.
Procedure Dijstra:
(* Đầu vào:
Đồ thị có hướng G=(v,E) với n đỉnh,
s ∈ V là đỉnh xuất phát, a[u,v], u,v ∈ V, ma trận trọng số;
Giả thiết: a[u,v]≥0, u,v ∈ V.
Đầu ra:
Khoảng cách từ đỉnh s đến tất cả các đỉnh còn lại d[v], v ∈ V.
Truoc[v], v ∈ V, ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v *)
Begin
(* Khởi tạo *)
for v ∈ V do
begin
d[v]:=a[s,v];
Truoc[v]:=s;
end;
d[s]:=0; T:=V{ s} ; (* T là tập các đỉnh cá nhãn tạm thời *)
(* Bước lặp *)
while T <> ∅ do
begin
tìm đỉnh u ∈ T thoả mãn d[u]=min{ d[z]:z ∈ T} ;
T:=T{u} ; (* Cố định nhãn của đỉnh u*)
For v ∈ T do
If d[v]>d[u]+a[u,v] then
Begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
End;
end;
End;
Định lý 7.1
Thuật toán Dijkstra tìm được đường đi ngắn nhất trên đồ thị sau thời gian cỡ O(n2).
Chứng minh.
Trước hết ta chứng minh là thuật toán tìm được đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị. Giả sử ở một bước lặp nào đó các nhãn cố định cho ta độ dài các đường đi ngắn nhất từ s đến các đỉnh có nhãn cố định, ta sẽ chứng minh rằng ở lần gặp tiếp theo nếu đỉnh u* thu được nhãn cố định d(u*) chính là độ dài đường đi ngẵn nhất từ s đến u*.
Ký hiệu S1 là tập hợp các đỉnh có nhãn cố định còn S2 là tập các đỉnh có nhãn tạm thời ở bước lặp đang xét. Kết thúc mỗi bước lặp nhãn tạm thời d(u*) cho ta độ dài của đường đi ngắn nhất từ s đến u* không nằm trọng trong tập S1, tức là nó đi qua ít nhất một đỉnh của tập S2. Gọi z ∈ S2 là đỉnh đầu tiên như vậy trên đường đi này. Do trọng số trên các cung là không âm, nên đoạn đường từ z đến u* có độ dài L > 0 và
d(z) < d(u*) – L < d(u*).
Bất đẳng thức này là mâu thuẫn với cách xác định đỉnh u* là đỉnh có nhãn tạm thời nhỏ nhất. Vậy đường đi ngắn nhất từ s đến u* phải nằm trọn trong S1, và vì thế, d[u*] là độ dài của nó. Do ở lần lặp đầu tiên S1 = {s} và sau mỗi lần lặp ta chỉ thêm vào một đỉnh u* nên giả thiết là d(v) cho độ dài đường đi ngắn nhất từ s đến v với mọi v ∈ S1 là đúng với bước lặp đầu tiên. Theo qui nạp suy ra thuật toán cho ta đường đi ngắn nhất từ s đến mọi đỉnh của đồ thị.
Bây giờ ta sẽ đánh giá số phép toán cần thực hiện theo thuật toán. Ơû mỗi bước lặp để tìm ra đỉnh u cần phải thực hiện O(n) phép toán, và để gán nhãn lại cũng cần thực hiện một số lượng phép toán cũng là O(n). thuật toán phải thực hiện n-1 bước lặp, vì vậy thời gian tính toán của thuận toán cỡ O(n2).
Định lý được chứng minh.
Khi tìm được độ dài của đường đi ngắn nhất d[v] thì đường đi này có thể tìm dựa vào nhãn Truoc[v], v∈ V, theo qui tắc giống như chúng ta đã xét.
Ví dụ 7.2
Tìm đường đi ngắn nhất từ 1 đến các đỉnh còn lại của đồ thị ở hình 2.
Hình 7.2 Minh họa thuật toán Dijkstra.
Kết quả tính toán theo thuật toán được trình bày theo bảng dưới đây. Qui ước viết hai thành phần của nhãn theo thứ tự: d[v]. Đỉnh được đánh dấu * là đỉnh được chọn để cố định nhãn ở bước lặp đang xét, nhãn của nó không biến đổi ở các bước tiếp theo, vì thế ta đánh dấu -.
| Bước lặp | Đỉnh 1 | Đỉnh 2 | Đỉnh 3 | Đỉnh 4 | Đỉnh 5 | Đỉnh 6 |
| Khởi tạo | 0,1 | 1,1* | ∞ ,1 | ∞ ,1 | ∞ ,1 | ∞ ,1 |
| 1 | - | - | 6,2 | 3,2* | ∞ ,1 | 8,2 |
| 2 | - | - | 4,4* | - | 7,4 | 8,2 |
| 3 | - | - | - | 7,4 | 5,3* | |
| 4 | - | - | - | 6,6* | - |
Chú ý:
1) Nếu chỉ cần tìm đường đi ngắn nhất từ s đến một đỉnh t nào đó thì có thể kết thúc thuật toán khi đỉnh t trở thành có nhãn cố định.
2) Tương tự như trong mục 7.2, dễ dàng mô tả thuật toán trong trường hợp đồ thị cho bởi danh sách kề. Để có thể giảm bớt khối lượng tính toán trong việc xác định đỉnh u ở mỗi bước lặp, có thể sử dụng thuật toán Heasort (tương tự như trong bài 5 khi thể hiện thuật toán Kruskal). Khi đó có thể thu được thuật toán với độ phức tạp tính toán là O(m log n).
