다익스트라 알고리즘(Dijkstra), 가중치가 있는 그래프의 최단 경로

다익스트라(Dijkstra) 알고리즘

 

  가중치가 없는 그래프인 경우 BFS를 수행하면 시작점으로 부터 각 정점 까지의 최단 거리를 구할 수 있다. 만약 그래프의 간선이 가중치를 갖는다면 BFS를 이용하여 최단거리를 구하는것은 불가능 하다.

간선의 가중치로 인해 시작점에서 도착점 까지 거치는 간선의 갯수가 해당 경로의 거리가 아니기 때문이다.

거치는 간선의 갯수와는 관계없이 간선의 가중치의 합이 최소가 되는 경로가 최단 경로가 된다.

 

  이와 같은 문제를 해결하기 위한 알고리즘이 여러개 있지만 이 중 그래프에 음수 사이클이 없는 경우 단일 시작점 최단 경로를 구하는 대표적인 알고리즘이 다익스트라 알고리즘이다.

 

  해당 그래프의 최단경로를 구하기 위하여 다익스트라 알고리즘을 구현 하고자 한다면 우선순위 큐와 시작점부터 해당 정점까지의 최단거리를 저장하는 배열이 선언 되어야 된다. 알고리즘은 아래와 같은 의사 코드를 따른다. 

//typedef vector<int> vi;

//typedef pair<int, int> ii;

1. vi dist(V, INF);    dist[s] = 0;    //s는 시작점이다. s부터 s까지의 거리는 0이다. 

2. pq선언, pq에는 정점과 시작점에서 정점사이의 거리 쌍이 pair의 형태로 저장되고 
거리가 작은 순으로 그리고 거리가 같을시 정점의 번호가 빠른순으로 저장된다.

3. pq.push(0, s)

4. while : pq가 빌때까지 반복

5.     ii front = pq.top(),    pq.pop()

6.     u = front.second, d = front.first    //가장 거리가 가까운 정점과 거리

7.     if(d > dist[u]) continue    //relax(완화)

8.     for : u와 인접한 정점을 순회

9.     if(dist[u] + v.distance < dist[v])

10.   dist[v] = dist[u] + v.distance    //u와 인접한 정점

11.   push ii(v.distance, v) to pq     //v와 시작점부터 v까지의 거리 쌍을 pq에 삽입

 

  간선에 가중치가 있을지라도 최단경로를 구하는 문제에는 역시 최적 구분 구조가 성립된다. 다시 말해서 최단 경로의 부분 경로들 역시 해당 구간의 최단 경로라는 사실이다.

최단 경로 상에 모든 정점들쌍의 최단경로는 전체 경로의 부분집합에 해당 된다. 때문에 9, 10, 11과 같은 과정은 꽤나 직관적이다. pq에 들어 있는 정점들의 시작점으로 부터의 거리가 dist에 저장되어진 값보다 더 작을때 최단거리는 갱신된다.

 

  다시 말해서 최단 경로가 갱신되어지기 위해서는 경로 상의 정점이 pq에 삽이 되어져야 된다. 해당 구간의 의사코드가 위의 작업을 수행한다. 

 

  이 글을 읽는 독자라면 다른 사람의 코드를 참조하지 않고 우선순위큐를 이용해서 다익스트라 알고리즘을 직접 구현해 보기를 바란다.

 

  그때 느끼는 에로 사항이 바로 7번 코드의 부제이다. 다시말해 pq에 정점 u가 삽입되어 있다고 가정하자. 하지만 알고리즘 수행 도중에 pq에서 더짧은 u까지의 경로가 발견된다면(9, 10, 11에서) pq에는 u가 있음에도 불구하고 u가 다시 push 될것이다.

즉 pq에 여러개의 같은 정점이 존재할 수 있다는 것이다. 이는 pq에 저장된 모든 정점이 유용하지 않다는 것이다.

이는 pq에는 무시되어야 될 정점이 있다는것을 의미한다.

pq에 정점 u가 3개라면 3개중에서 u까지의 거리가 가장 짧은 페어쌍을 제왜한 두개는 의미가 없다. 즉 무시된다.

 

이를 '느긋한 삭제' 라고 한다.

 

  더 짧은 경로가 확인 되는 순간에 pq에서 해당정점의 페어쌍을 제거하고 새롭게 push하는것은 오버헤드가 너무 심하기 때문에 이와 같은 처리를 하는 것이다.

이는 pq내부에 해당정점의 페어쌍이 어디 존재하는 지에 대한 탐색이 불필요함을 의미한다.

탐색 도중에 정점들의 최단 거리가 계속해서 작아지는 것을 완화(relax)된다고 한다.

 

 

Dijkstra Algorithm's Code

 

typedef vector<int> vi;

typedef pair<int, int> ii;

vi dist(V, INF);  dist[s] = 0;  //INF는 10억쯤, 시작점 부터 해당 점정 까지의 최단 거리

priority_queue<ii, vector<int>, greater<ii> > pq;    pq.push(0, s);    //s는 시작점

while(!pq.empty()) {

ii front = pq.top();    pq.pop();

int d = front.first, u = front.second;

if(d > dist[u])    continue;    //d는 dist[u]와 같거나 크다.

for(int i = 0; i < (int)adjList[u].size(); ++i) {

ii v = adjList[u][i];

if(dist[u] + v.second < dist[v.first]) {

dist[v.first] = dist[u] + v.second;

pq.push(ii(dist[v.first], v.first));

}     }     }

 

Time Complexity of Dijkstra Algorithm

 

  다익스트르아 알고리즘은 우선순위큐에 정점이 들어가고 나올때 O(logV)의 오버헤드가 발생한다. 결과적으로 최종 시간복잡도는 pq에 몇개의 정점이 들어가지에 의해 결정될 것이다.

정점은 총 V개이고 해당 정점은 여러번 들어갈 수 있다. 이때 정점이 방문되는 루트는 이전 정점을 거치게 된다.

이전 정점이 같다면 또다시 정점이 고려되어질 이유가 없다. 이유는 해당 문제는 최적 구분 구조가 성립하기 때문이다.

 

  간선을 고려한다면 이같은 중복을 피할 수 있다. 해당 정점은 간선을 통해서 출입이 가능하다.

총 정점의 갯수는 V개이고 간선이 E개이다. 이때 중복해서 방문되는 횟수는 E이하일 것이다.

그이유는 이미 거친 간선을 통해 해당정점을 다시 방문할 필요가 없기 때문이다.

이는 사이클을 의미하며 해당 알고리즘이 다루는 그래프는 음수 사이클이 존재하지 않는다.

음수 사이클이 아니라면 최단경로가 사이클을 가질 가능성은 없다.

 

  결과적으로 해당 알고리즘의 분할상환분석을 통한 최종 시간복잡도는 O((V + E)logV)이다.