Bài toán chính cũng giống như bài trước, từ nút xuất phát đến bất kỳ nút nào khác, hãy tìm những khoảng cách nhỏ nhất. Trong bài toán này, điểm khác biệt chính là đồ thị được biểu diễn bằng ma trận kề. (Ma trận chi phí và ma trận kề tương tự cho mục đích này).
Đối với biểu diễn danh sách kề, độ phức tạp thời gian là O (V ^ 2) trong đó V là số nút trong biểu đồ G (V, E)
Đầu vào và Đầu ra
Input: The adjacency matrix:Output: 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 cho mỗi đỉnh, danh sách tiếp theo để lưu trữ nút nào đến tiếp theo và đỉnh gốc hoặc đỉnh bắt đầu.
Đầu ra - Các đường đi ngắn nhất từ đầu đến tất cả các đỉnh khác.
Begin create a status list to hold the current status of the selected node for all vertices u in V do status[u] := unconsidered dist[u] := distance from source using cost matrix next[u] := start done status[start] := considered, dist[start] := 0 and next[start] := φ while take unconsidered vertex u as distance is minimum 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 End
Ví dụ
#include<iostream>
#define V 7
#define INF 999
using namespace std;
// Cost matrix of the graph
int costMat[V][V] = {
{0, 3, 6, INF, INF, INF, INF},
{3, 0, 2, 1, INF, INF, INF},
{6, 2, 0, 1, 4, 2, INF},
{INF, 1, 1, 0, 2, INF, 4},
{INF, INF, 4, 2, 0, 2, 1},
{INF, INF, 2, INF, 2, 0, 1},
{INF, INF, INF, 4, 1, 1, 0}
};
int minimum(int *status, int *dis, int n) {
int i, min, index;
min = INF;
for(i = 0; i<n; i++)
if(dis[i] < min && status[i] == 1) {
min = dis[i];
index = i;
}
if(status[index] == 1)
return index; //minimum unconsidered vertex distance
else
return -1; //when all vertices considered
}
void dijkstra(int n, int *dist,int *next, int s) {
int status[V];
int u, v;
//initialization
for(u = 0; u<n; u++) {
status[u] = 1; //unconsidered vertex
dist[u] = costMat[u][s]; //distance from source
next[u] = s;
}
//for source vertex
status[s] = 2; dist[s] = 0; next[s] = -1; //-1 for starting vertex
while((u = minimum(status, dist, n)) > -1) {
status[u] = 2;//now considered
for(v = 0; v<n; v++)
if(status[v] == 1)
if(dist[v] > dist[u] + costMat[u][v]) {
dist[v] = dist[u] + costMat[u][v]; //update distance
next[v] = u;
}
}
}
main() {
int dis[V], next[V], i, start = 0;
dijkstra(V, dis, next, start);
for(i = 0; i<V; i++)
if(i != start)
cout << start << " to " << i <<", Using: " << next[i] << ",
Cost: " << dis[i] << endl;
} Đầ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