요약

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

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

구현

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

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

~~~ c++

#include
#include
#include
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 > > &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;

}
~~~