History: Dijkstra's algorithm

요약

유명한 전산학자인 E. W. Dijkstra가 고안한 그래프 상의 최단경로 문제를 풀기 위한 알고리즘이다. 특징은 다음과 같다.

  • 그래프 상의 하나의 정점을 기준으로, 나머지 정점들에 대한 최단 경로를 구할 때 사용된다(Single-source shortest-paths).
  • 음수 가중치를 가진 사이클 경로가 존재할 경우 사용할 수 없다.
  • 일반적인 알고리즘 책에 나온 구현을 따르면 O(|V|2)의 시간 복잡도로 구현이 되어있으나, 인접 리스트와 우선 순위 큐를 사용할 경우 O(|E|log|V|)의 시간 복잡도로 구현 할 수 있다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수를 뜻한다.

구현

다음 코드들은 Til the Cows Come Home라는 전형적인 Dijkstra's algorithm으로 해결할 수 있는 문제의 해법이다.

인접 리스트를 이용한 일반적인 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int inf = 987654321;

/* 
G는 인접리스트를 뜻한다. G[i] 는 i번 정점에 연결된 간선의 정보(pair의 first)와 가중치(pair의 second)를 담고 있다.
start는 시작점을 의미한다.

결과는 vector로 반환되며, vector의 i번째 원소는 start부터 i번 정점 까지의 최단 거리를 뜻한다.
*/
vector< int > dijkstra( const vector< vector< pair<int,int> > > &G, const int start ) {
    const int N = (int)G.size();

    vector< int > dist( N, inf );
    vector< bool > used( N, false );
    dist[ start ] = 0;

    while( true ) {
        int current = -1;

        for( int i = 0 ; i < N ; ++i ) {
            if( used[i] ) continue;
            if( current == -1 || dist[current] > dist[i] ) {
                current = i;
            }
        }
        if( current == -1 ) break;
        used[ current ] = true;

        const vector< pair<int,int> > &edges = G[current];

        for( int i = 0 ; i < edges.size() ; ++i ) {
            int next = edges[i].first;
            dist[ next ] = min( dist[next], dist[current] + edges[i].second );
        }

    }

    return dist;

}

int main() {
    int E, V;

    cin >> E >> V;

    vector< vector< pair<int,int> > > G( V );
    for( int i = 0 ; i < E ; ++i ) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;

        G[u].push_back( make_pair(v,w) );
        G[v].push_back( make_pair(u,w) );
    }

    vector<int> ret = dijkstra( G, 0 );

    cout << ret[V-1] << endl;
}