Định nghĩa
Thuật toán Dijkstra tìm đường đi ngắn nhất từ một nút cụ thể (nguồn) đến mọi nút khác trong đồ thị liên thông. Tạo shortest path tree gốc tại nguồn. Dùng nhiều trong mạng máy tính để tạo tuyến tối ưu, giảm chi phí định tuyến.
Dijkstra's Algorithm
Input: đồ thị mạng; nguồn s. Output: shortest path tree spt[] gốc s.
Khởi tạo
- dist[] size |V|: dist[s]=0, dist[u]=∞ (u≠s).
- Q: chứa tất cả node. Khi kết thúc Q rỗng.
- S: tập rỗng, thêm node đã thăm. Khi kết thúc S chứa tất cả node.
- Lặp enquanto Q không rỗng:
- Lấy u từ Q có dist[u] nhỏ nhất, u∉S. Lần đầu lấy s.
- Thêm u vào S (đánh dấu visited).
- Với mỗi v kề u: nếu dist[u]+weight(u,v) < dist[v] → cập nhật dist[v].
- dist[] chứa shortest path từ s đến mọi node.
Ví dụ minh họa
Xét đồ thị节点 A-G, cạnh có trọng số như hình.
Khởi tạo: dist[7]={0,∞,∞,∞,∞,∞,∞}, Q={A,B,C,D,E,F,G}, S=∅.
Pass 1: chọn A (dist=0) vào S. Cập nhật B=5, C=6. dist={0,5,6,∞,∞,∞,∞}, Q={B,C,D,E,F,G}, S={A}.
Pass 2: chọn B (dist=5) vào S. Cập nhật C=6 (giữ), D=12, E=13. dist={0,5,6,12,13,∞,∞}, Q={C,D,E,F,G}, S={A,B}.
Pass 3: chọn C (dist=6) vào S. Cập nhật D=8, F=10. dist={0,5,6,8,13,10,∞}, Q={D,E,F,G}, S={A,B,C}.
Pass 4: chọn D (dist=8) vào S. Cập nhật E=10, F=10, G=18. dist={0,5,6,8,10,10,18}, Q={E,F,G}, S={A,B,C,D}.
Pass 5: chọn E (dist=10) vào S. Cập nhật G=13. dist={0,5,6,8,10,10,13}, Q={F,G}, S={A,B,C,D,E}.
Pass 6: chọn F (dist=10) vào S. G qua F = 13 (không cập nhật). dist={0,5,6,8,10,10,13}, Q={G}, S={A,B,C,D,E,F}.
Pass 7: chọn G, Q rỗng, kết thúc. Shortest path tree từ A như hình ban đầu.