음이 아닌 가중치를 가진 그래프에서 단일 출발점(single source) 최단 경로를 구하는 알고리즘은 널리 다익스트라(Dijkstra) 알고리즘으로 알려져 있습니다. 이 문제에서는 인접 행렬(adjacency matrix)로 표현된 그래프 G(V, E)와 하나의 시작 정점(source vertex)이 주어지며, 다익스트라 알고리즘을 이용해 시작 정점에서 그래프의 다른 모든 정점까지의 최소 비용 경로를 찾습니다.
시작 노드에서 임의의 다른 노드까지 이동할 때 가장 작은 거리를 구하는 것이 목표입니다. 이 문제에서 그래프는 인접 행렬로 표현되며, 비용 행렬(cost matrix)과 인접 행렬은 이 목적에서 사실상 동일하게 취급됩니다.
입력과 출력 예시
입력 − 인접 행렬
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에서 각 정점까지의 최단 경로
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
여기서 Using은 해당 정점으로 가기 위해 직전에 거치는 노드를, Cost는 누적 최소 비용을 의미합니다.
알고리즘
dijkstraShortestPath(n, dist, next, start)
입력 − 전체 노드 수 n, 각 정점의 거리 리스트 dist, 다음에 방문할 노드를 저장하는 next 리스트, 시작 정점 start.
출력 − 시작 정점에서 나머지 모든 정점까지의 최단 경로.
Begin
선택된 노드의 현재 상태를 담을 status 리스트 생성
V의 모든 정점 u에 대해 반복:
status[u] := 미고려(unconsidered)
dist[u] := 비용 행렬 기준 시작점으로부터의 거리
next[u] := start
종료
status[start] := 고려됨(considered), dist[start] := 0, next[start] := φ
while 미고려 정점 중 dist가 최소인 u를 선택하는 동안:
status[u] := 고려됨
V의 모든 정점 v에 대해:
if status[v] = 미고려 then
if dist[v] > dist[u] + cost[u,v] then
dist[v] := dist[u] + cost[u,v]
next[v] := u
종료
종료
EndC++ 구현 예제
#include<iostream>
#define V 7
#define INF 999
using namespace std;
//그래프의 비용 행렬
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;//아직 고려되지 않은 정점 중 최소 거리
else
return -1;//모든 정점을 고려한 경우
}
void dijkstra(int n, int *dist,int *next, int s){
int status[V];
int u, v;
//초기화
for(u = 0; u<n; u++){
status[u] = 1;//미고려 정점
dist[u] = costMat[u][s];//시작점으로부터의 거리
next[u] = s;
}
//시작 정점 처리
status[s] = 2; dist[s] = 0; next[s] = -1;//-1은 시작 정점을 의미
while((u = minimum(status, dist, n)) > -1){
status[u] = 2;//이제 고려됨
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];//거리 갱신
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
위 결과에서 볼 수 있듯이, 다익스트라 알고리즘은 매 단계마다 아직 확정되지 않은 정점 중 거리가 가장 짧은 정점을 선택하고, 그 정점을 경유할 때 더 짧아지는 경로가 있는지 확인해 거리와 경로 정보를 갱신합니다. 이 과정을 모든 정점이 확정될 때까지 반복하면 시작 정점에서 그래프 내 모든 정점까지의 최단 경로와 최소 비용을 얻을 수 있습니다. 단, 이 알고리즘은 간선의 가중치가 음수가 아닌 경우에만 올바른 결과를 보장한다는 점에 유의해야 합니다.