개요
가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할수 있는 알고리즘이다.
비슷한 목적을 가진 알고리즘으로 Bellman-ford Algorithm이 있다.
시작 정점인 v1에서 집합 V-Y까지 최단 경로의 정점을 구해서 Y로 편입시켜나가는 방법이다.
High-level Algorithm
F = {};
Y = {v1};
While (the instance is not solved)
{
select a vertex v from V-Y, that has a shortest path from v1, using only vertices in Y as intermediate;
add the new vertex v to Y;
add the edge (on the shortest) that touches v to F;
if (Y == V)
the instance is solved;
}
Dijkstra's Algorithm
- neartest[i] = index of vertex v in Y such that the edge <v, vi> is the last edge on the current shortest path from v1 to vi using only vertices in Y as intermediate. v1에서 vi까지의 최단경로에서 vi직전의 정점 index.
- length[i] = length of the current shortest path from v1 to v2 using only vertices in Y as intermediates.
// n : 정점의 개수
// W[i][j] : i에서 j까지 edge cost. 이어져 있지 않으면 INF, i == j면 0 이다.
// F : 반환용 최단경로 Edge들.
void dijkstra (int n, const number W[][], set_of_edges& F)
{
index i, vnear; // 현재 V-Y중에 v1에서 최단경로로 갈수있는 vertex
edge e;
index nearest[2..n]; // vi와 Y를 연결하는 정점. vi와 이어져있는 경로.
number length[2..n]; // v1에서 vi까지 최단경로의 길이.
F = {};
for (i = 2; i <= n; i++)
{
nearest[i] = 1; // 가장 가까운 집합 Y 정점 초기값을 v1으로 둔다.
length[i] = W[1][i]; // 그에대한 실제 길이를 경로길이 초기값으로 둔다.
}
repeat( n-1 times )
{
min = INF;
for ( i = 2; i <= n; i++ )
{
if( 0 <= length[i] <= min ) // min으로 현재 vnear를 구한다.
{
min = length[i];
vnear = i;
}
}
e = edge from vertex indexed by nearest[vnear] to vertex indexed by vnear; // edge from nearest[vnear] to vnear
add e to F;
for ( i = 2; i <= n; i++ )
{
if (length[vnear] + W[vnear][i] < length[i])
{
length[i] = length[vnear] + W[vnear][i];
nearest[i] = vnear;
}
}
length[vnear] = -1;
}
}
Complexity
$T(n) = 2(n-1)^2 \in O(n^2)$