[Algorithm] Dijkstra's Algorithm

개요

가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구할수 있는 알고리즘이다.
비슷한 목적을 가진 알고리즘으로 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)$