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으로 해결할 수 있는 문제의 해법이다.

인접 리스트를 이용한 O(|V|2) 구현

#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;
}

인접리스트와 STL set을 이용한 O(|E|log|V|) 구현

다음 코드에서는 우선순위 큐(STL priority_queue)가 아닌 STL set을 이용한 구현을 사용하였는데, STL priority_queue의 경우 queue안에 있는 임의의 값을 찾아서 갱신 할 수 없기 때문에 많은 불편이 따른다. 허나 set의 경우 priority_queue와 유사하게 동작하면서 동시에 값을 갱신할 수 있기 때문에 상대적으로 편하게 구현할 수 있다.

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

const int inf = 987654321;
vector< int > dijkstra( const vector< vector< pair<int,int> > > &G, const int start ) {
    const int N = (int)G.size();

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

    set< pair<int,int> > pq;

    pq.insert( make_pair( 0, start ) );
    while( !pq.empty() ) {

        pair<int,int> top = *pq.begin();
        pq.erase(top);

        int current = top.second;

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

        for( int i = 0 ; i < edges.size() ; ++i ) {
            int next = edges[i].first;

            if( dist[next] > dist[ current ] + edges[i].second ) {
                pq.erase( make_pair( dist[next], next ) );
                pq.insert( make_pair( dist[current] + edges[i].second, next ) );
                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;
}

0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.