단일 소스 최단 경로 알고리즘(음수가 아닌 가중치)은 Dijkstra 알고리즘으로도 알려져 있습니다. 인접 행렬 표현이 있는 주어진 그래프 G(V,E)가 있으며 소스 정점도 제공됩니다. 그래프 G의 다른 정점에 대한 소스 정점 사이의 최소 최단 경로를 찾는 Dijkstra의 알고리즘입니다.
시작 노드에서 다른 노드까지 가장 작은 거리를 찾습니다. 이 문제에서 그래프는 인접 행렬을 사용하여 표현됩니다. (비용 매트릭스와 인접 매트릭스는 이를 위해 유사합니다.)
입력 − 인접 행렬 −
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
출력 -
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
알고리즘
dijkstraShortestPath(n, dist, 다음, 시작)
입력 − 총 노드 수 n, 각 정점에 대한 거리 목록, 다음에 올 노드를 저장할 다음 목록, 시드 또는 시작 정점.
출력 − 시작에서 다른 모든 정점까지의 최단 경로.
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
예시(C++)
#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;
} 출력
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