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