다익스트라(Dijkstra) 알고리즘이란?
최단 경로를 구하는 알고리즘 중 하나.
단일 소스(하나의 노드)로부터 출발하여 나머지 노드까지 가는 데 최단 경로를 구하는 방법이다.
단, 음수 가중치가 있을 경우에는 사용 불가
알고리즘 동작 방식
다익스트라 알고리즘은 하나의 노드에서 그 노드와 가장 가까운 경로를 fix하는 데서 출발한다.
최소 신장 트리를 찾는 알고리즘 중 prim 알고리즘과 유사한데, 차이점이 있다면 prim은 현재 노드에서 가중치가 적은 노드를 찾는 반면 다익스트라는 시작 노드로부터 가중치가 적은 경로의 노드를 골라야 한다는 데에 있다.
좀 더 쉬운 이해를 위해 예시를 보도록 하자.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 4 | 2 | 1 | INF | INF | INF |
시작노드 0을 기준으로 나머지 노드로의 가중치(최소값)는 위의 표와 같다.
0: 자기 자신이므로 가중치의 값은 0이 된다.
1: 0노드에서 바로 갈 수 있는 경로의 가중치이므로 4가 된다.
2: 0노드에서 바로 갈 수 있는 경로의 가중치이므로 2가 된다.
3: 0노드에서 바로 갈 수 있는 경로의 가중치이므로 1이 된다.
4, 5, 6: 0노드와 아직 직접적으로 이어져 있진 않으므로 가중치를 알 수 없기에 INF
위의 가중치 중 가장 작은 값이 1이므로 0->3 경로는 fix한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | INF | 8 | INF |
이제는 0 뿐만 아니라 3노드에서 갈 수 있는 경로까지 고려할 수 있다.
따라서 이전 표에서 1노드와 5노드로 가는 경로의 가중치값(최소값)이 변경이 된다.
1노드의 경우, 3노드를 거쳐 가는 경로의 가중치 3(1+2)이 0노드에서 바로 가는 경로의 가중치 4보다 작은 값이므로 표의 값을 변경해준다.
5노드의 경우도 마찬가지로 3노드를 거쳐 5노드로 가는 경로가 보이므로 가중치를 INF에서 8(1+7)로 변경해준다.
위의 값들 중 0과 3노드로의 경로를 제외하고 가장 가중치가 낮은 경로는 2노드로 가는 경로이므로 이 경로또한 fix해준다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | 5 | 8 | INF |
2노드에서의 경로까지 고려해도 되자 가중치를 계산할 수 있는 노드가 하나 더 늘었다.
4노드는 0->2->4를 거칠 수 있으므로 4노드로 가는 경로의 가중치를 INF에서 5(2+3)로 변경해준다.
0, 3, 2노드가 fix된 상태에서 가중치가 가장 적은 경로는 1노드로 가능 경로이므로 1노드로의 경로를 fix해준다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | 5 | 8 | INF |
fix된 경로를 제외하고 가장 작은 가중치의 경로는 4노드로 가는 경로이므로 이를 fix한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | 5 | 8 | INF |
5노드로 가는 경로는 0->2->4->5와 0->3->5 경로 2가지가 있다.
전자의 경우 가중치 값이 9인 반면, 후자의 경우 가중치 값이 8이므로 현재 값을 변경하지는 않는다.
남은 경로 중 가중치 값이 가장 적은 경로가 5노드로 가는 경로이므로 이 또한 fix한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | 5 | 8 | 9 |
5노드를 fix하면서 6노드로 가는 경로의 가중치를 계산할 수 있게 되었다.
'5노드로의 가중치 + 5노드에서 6노드로 가는 데 드는 가중치' 이므로 9가 된다.
이제 남은 경로는 6노드로 가는 경로 하나뿐이므로 이를 fix한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 3 | 2 | 1 | 5 | 8 | 9 |
일련의 과정을 거쳐 나온 이 상태가 다익스트라로 얻은 0노드로부터의 최단 경로가 된다.
코드 작성
이제 기본적인 동작 방식은 확인했으니 이를 코드로 작성해보자.
1) 순차탐색
시간복잡도 O(n^2)가 요구되는 구현이다.
방문하지 않은 노드 중 최단 경로인 노드를 찾는 방법을 순차탐색으로 진행한 것이다.
최단 경로인 노드를 찾기 위해 n만큼의 값 비교와 방문 여부를 확인해줘야 하며 그 노드에서 n-1개의 노드로 가는 최단 경로를 갱신해줘야 한다.
using System;
namespace ConsoleApp
{
internal class Program
{
const int INF = 100000000;
static void Main(string[] args)
{
int[,] weight =
{
{0,4,2,1, INF, INF, INF},
{4,0,INF,2,INF,INF,INF },
{2,INF,0,INF,3,INF,INF },
{1,2,INF,0,INF,7,INF },
{INF,INF,3,INF,0,4,INF },
{INF,INF,INF,7,4,0,1 },
{INF,INF,INF,INF,INF,1,0 }
};
int startNode = 0;
int[] dist = new int[7];
for (int i = 0; i < dist.Length; i++)
dist[i] = weight[0, i];
bool[] visited = { false, false, false, false, false, false, false };
Dijkstra(weight, dist, visited, startNode);
for(int i = 0; i < dist.Length; i++)
{
Console.WriteLine("{0}: {1}", i, dist[i]);
}
}
static void Dijkstra(int[,] w, int[] d, bool[] v, int s)
{
for(int i = 0; i < d.Length; i++)
{
int node = GetNode(d, v);
int dist = d[node];
v[node] = true;
for(int j = 0; j < w.GetLength(1); j++)
{
if (dist + w[node, j] < d[j])
{
d[j] = dist + w[node, j];
}
}
}
}
static int GetNode(int[] d, bool[] v)
{
int nodeIdx = 0;
int minWeight = INF;
for(int i = 0; i < d.Length; i++)
{
if (minWeight > d[i] && !v[i])
{
minWeight = d[i];
nodeIdx = i;
}
}
return nodeIdx;
}
}
}
결과
