Trong mạng máy tính, thuật toán đường đi ngắn nhất nhằm tìm đường tối ưu giữa các nút mạng để chi phí định tuyến tối thiểu. Chúng là ứng dụng trực tiếp của thuật toán shortest path trong lý thuyết đồ thị.
Giải thích
Xét mạng gồm N đỉnh (node/thiết bị) kết nối bởi M cạnh (đường truyền). Mỗi cạnh có trọng số: khoảng cách vật lý hoặc độ trễ truyền. Mục tiêu: tìm tuyến giữa bất kỳ cặp đỉnh nào sao cho tổng trọng số cạnh nhỏ nhất. Nếu trọng số bằng nhau → tìm tuyến ít hop nhất.
Các thuật toán Shortest Path phổ biến
- Bellman Ford Algorithm
- Dijkstra Algorithm
- Floyd Warshall Algorithm
Các phần sau mô tả chi tiết từng thuật toán.
Bellman Ford Algorithm
Input: đồ thị mạng; nguồn s. Output: đường đi ngắn nhất từ s đến mọi node khác.
- Khởi tạo dist[s]=0, các node khác = ∞. Mảng dist[] kích thước |V|.
- Lặp |V|-1 lần cho mỗi node trừ s:
- Với mỗi cạnh nối u, v: nếu dist[v] > dist[u] + weight(u,v) → cập nhật dist[v].
- dist[] chứa shortest path từ s đến mọi node.
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.
Floyd Warshall Algorithm
Input: ma trận chi phí kề adj[][]. Output: ma trận chi phí shortest path cost[][] giữa mọi cặp node.
- Khởi tạo cost[][]: nếu adj[][] rỗng → ∞, ngược lại = adj[][].
- N = |V|.
- Lặp k=1..N, i=1..N, j=1..N: nếu cost[i][k]+cost[k][j] < cost[i][j] → cập nhật cost[i][j].
- cost[][] chứa chi phí ngắn nhất từ i đến j.