Thuật toán đường đi ngắn nhất đơn nguồn (trọng số không âm) gọi là Dijkstra. Cho đồ thị G(V,E) với ma trận kề và đỉnh nguồn. Dijkstra tìm đường đi ngắn nhất từ nguồn đến mọi đỉnh khác.

Từ nút bắt đầu đến bất kỳ nút nào, tìm khoảng cách nhỏ nhất. Đồ thị biểu diễn bằng ma trận kề (ma trận chi phí tương tự).
Đầu vào − Ma trận kề:
0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ∞ 6 2 0 1 4 2 ∞ ∞ 1 1 0 2 ∞ 4 ∞ ∞ 4 2 0 2 1 ∞ ∞ 2 ∞ 2 0 1 ∞ ∞ ∞ 4 1 1 0
Đầu ra −
0 to 1, Using: 0, Cost: 3 0 to 2, Using: 1, Cost: 5 0 to 3, Using: 1, Cost: 4 0 to 4, Using: 3, Cost: 6 0 to 5, Using: 2, Cost: 7 0 to 6, Using: 4, Cost: 7
Thuật toán
dijkstraShortestPath(n, dist, next, start)
Đầu vào − Tổng số nút n, danh sách khoảng cách, danh sách next, đỉnh bắt đầu.
Đầu ra − Các đường đi ngắn nhất từ start đến mọi đỉnh khác.
Begin
tạo danh sách status lưu trạng thái nút được chọn
for all vertices u in V do
status[u] := unconsidered
dist[u] := khoảng cách từ nguồn dùng ma trận chi phí
next[u] := start
done
status[start] := considered, dist[start] := 0, next[start] := φ
while lấy đỉnh unconsidered u có khoảng cách nhỏ nhất do
status[u] := considered
for all vertex v in V do
if status[v] = unconsidered then
if dist[v] > dist[u] + cost[u,v] then
dist[v] := dist[u] + cost[u,v]
next[v] := u
done
done
done
EndVí dụ (C++)
#include#define V 7 #define INF 999 using namespace std; int costMat[V][V] = { ... }; int minimum(int *status, int *dis, int n){ ... } void dijkstra(int n, int *dist, int *next, int s){ ... } main(){ ... }
Đầu ra
0 to 1, Using: 0, Cost: 3 0 to 2, Using: 1, Cost: 5 0 to 3, Using: 1, Cost: 4 0 to 4, Using: 3, Cost: 6 0 to 5, Using: 2, Cost: 7 0 to 6, Using: 4, Cost: 7