Dijkstra Algorithm

앞서 소개한 벨만포드보다 향상된 기법(?)의 다익스트라 알고리즘에대해 알아보자.

1. 다익스트라 알고리즘 소개

먼저 다익스트라 알고리즘은 어떠한 Edge(간선) 도 음의 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.

다익스트라 알고리즘이 벨만포드 보다 빠른 경우는 O(|E|log|V|) 의 시간 복잡도 내에 최단 경로를 찾을 수 있기 때문이다.

이는 벨만포드 알고리즘의 시간복잡도 O(|E||V|) 보다 빠른 시간을 갖는다.

다익스트라 알고리즘이 어떤 식으로 구현하느냐에 따라 O(|E|log|V|)나 O(|E||V|)의 시간 복잡도 둘다를 가질수 있다.

어떻게 하면 O(|E|log|V|)의 시간복잡도를 갖는지는 아래에 설명해 놓았다.

2. 다익스트라 알고리즘 사용시기

다익스트라 알고리즘은 이러한 가정을 밑바탕으로 깔고간다, “현재 노드에서 가장 가까운 노드를 거쳐서 가는 다음 노드들은 거쳐진 노드들 보다 거리가 멀다.”

이러한 가정은 당연해 보이지만 벨만 포드와 다르게 중요한 제한점 하나를 두게 된다. 앞서 말했지만 “간선이 음의 가중치를 갖지 않는다”라는 조건이다.

이제 벨만포드 알고리즘과 사용시기를 구분해서 사용할수 있을것이다. 물론 벨만포드알고리즘은 음수, 양수 가중치에 상관 없이 쓰일 수있지만, 양수일경우 더 빠른 다익스트라 알고리즘을 두고 벨만포드 알고리즘을 사용하는 사람은 없지 않는가 ?

3. 다익스트라 알고리즘 동작

다익스트라 알고리즘은 다음과 같은 절차를 따른다.

최단거리가 확정된 노드와 인접해 있는 노드를 갱신한다.
1.에서 사용한[최단거리가 확정된 노드]는 더이상 사용하지 않는다.
모든 노드가 최단거리를 구하는데 사용될때까지 1,2 번을 반복한다.

위 그림을 따라 천천히 설명해 보겠다.

(a) 처음시작점 s부분이 0으로 초기화 되어있고, 다른 Vertex에대한 거리정보는 INFINITY 값으로 지정되어 있다.
(b) 다음 시작지점에 인접해있는 Vertex 중 가장 가까운 거리(5)를 갖는 y로 가서 원래의값(INFINITY) 과 s->y(5)+ s(0) 의 결과를 비교해 더작은 값으로 갱신해준다. 다음 역시 인접해있는 Vertex 인 t에 대해서도 같은 절차를 실행한다.
(C) 다음으로 최단거리를 갖는 갱신된 y로 가서 과정(b)에서 실행한 것과같이 y의 인접 Vertex 값들을 갱신한다.
(d) 갱신된 결과 다음으로 최단거리를 갖는 z로 가서 과정 (b),(c) 와 같은 절차를 시행한다.
(e) 다음 최단거리 t로 가서 같은 절차를 실행
(f) 마지막 Vertex 에대해 검사하고 더이상 검사할 Vertex 가 없기 때문에 시행을 종료한다.

위의 과정을 천천히 그림에 따라 이해했다면 다익스트라 알고리즘 동작 과정을 이해한 것이다.

4. 다익스트라 알고리즘 코드 구현

다익스트라 알고리즘은 위의 동작과정을 보면 알겠지만 거리가 최소인 Vertex 를 뽑아오는 과정과 , 그 Vertex 로부터 인접한 Vertex 까지의 거리를 갱신하는 과정 두가지로 구분할 수있다.

먼저 인접 행렬을 통해 구현한 간단하고 원초적이고 기본적인 ? 소스 예제를 보자

#include<iostream>
#include<algorithm>

#define MAX_V 1000                                    //MAX VERTEX

using namespace std;

int cost[MAX_V][MAX_V];                                //cost[i][j]는 변 edge=(i,j)의 가중치가 저장되어 있다고 가정 (존재하지 않으면 INF)
int distance[MAX_V];
bool used[MAX_V];
int verCnt;                                            //vertex Count

void dijkstra(int start){
    fill(distance, distance + verCnt, INFINITY);     // 모든 노드들에 대한 거리를 INF 값의로 초기화.
    fill(used, used + verCnt, false);                 // 모든 노드들이 방문되었는지를 기록.
    distance[start] = 0;

    while (true){
        int vertex = -1;
        //Vertex 숫자만큼 순회 하면서, 방문되지 않았고, 거리가 최소인 vertex를 찾는다. 여기서 결국 used가 더이상없으면 vertex 값은 -1 그대로 나온다.
        for (int i = 0; i < verCnt; i++){
            if (!used[u] && (v == -1 || distance[i] < distance[vertex])){
                vertex = i;
            }
        }
        //갱신될 vertex 가 더이상 없다면 루프를 종료..
        if (vertex == -1){
            break;
        }
        used[vertex] = true;    //선택된 vertex 의 used 상태를 갱신해준다.
        for (int i = 0; i < verCnt; i++){
            distance[i] = min(distance[i], distance[i] + cost[vertex][i]);
        }

    }
}

주석을 잘읽어 보면서 코드를 읽어보기를 바란다.
인접행렬을 통해 구현해 보았는데, 복잡도를 계산해보니 while문 내부에 |V| while문 종료하는 조건을 살펴본 결과 모든 vertex를 방문해봐야하므로 |V| 결국 O(|V||V|)의 복잡도를 갖는것을 확인하였다.

여기서 모든 Vertex들을 들려 갱신하는 것은 복잡도를 개선하는데 더 좋은 방밥이 없지만, 거리가 최소인 Vertex를 뽑아오는 과정은 heap을 이용하면 log 시간만에 처리할수 있다. 결국 O(|E|log|V|) 의 복잡도를 갖을수있게 되는데 그이유는 아래의 개선된 코드를 보자

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>

#define MAX_V 1000
using namespace std;
struct edge{
    int cost;
    int to;
};
typedef pair<int, int> P;                            //pair 의 first 는 최단거리 second는 노드번호

int V;                                                //Vertex  Count
vector<edge> G[MAX_V];
int dis[MAX_V];

void dijkstra(int start){
    priority_queue<P, vector<P>, greater<P>> que;    //우선순위 큐를 통해 최소힙처럼 쓸 data structure 를 준비 , greater 를 쓰면 frst 값이 작은순으로 가져올수 있다.
    fill(dis, dis + V, INFINITY);                    //각노드 까지의 거리를 INFINITY 값으로 초기화
    que.push(P(0, start));                            //첫번째 노드는 거리 값 0 을 갖는다. 그노드를 내가만든 우선순위 큐에 넣어준다.
    while (!que.empty()){                            //우선순위 큐 가 비어있을 때까지 루프를 돈다.
        P p = que.top();                            //우선순위 큐의 top의 요소를 가져온다.
        que.pop();                                    //pop
        int vertex = p.second;                        //vertex 번호 를 가져온다.    
        if (dis[vertex] < p.first)continue;
        //인접 리스트를 순회하면서 거리 비교후 거리가 갱신되면 우선순위 큐에 push한다.
        for (int i = 0; i < G[vertex].size(); i++){        
            edge e = G[vertex][i];                        
            if (dis[e.to]> dis[vertex] + e.cost){
                dis[e.to] = dis[vertex] + e.cost;
                que.push(P(dis[e.to], e.to));
            }
        }
    }
}

위 코드는 인접리스트와 우선순위 큐를 이용해 만든 다익스트라 알고리즘이다. 이렇게하면 push 과정에서 log|V| 시간 그위에 인접리스트 순회하는데 상수시간 , 큐의 요소를 뽑는데 |E| 따라서 O(|E|log|V|) 가 걸림을 알수있다.

5. 참고 문제

BOJ 1753- 최단 경로
https://www.acmicpc.net/problem/1753
BOJ 1238 -파티
https://www.acmicpc.net/problem/1238

6. A*

저번학기에 A* 알고리즘을 배워서 경로탐색에 최적화된 알고리즘이라 배웠는데 다익스트라 알고리즘과 비교해보고 싶었다.

하지만 다익스트라 알고리즘을 공부하고 나니 둘은 비교 대상이 아니였다. A* 알고리즘은 각간선의 가중치를 fhat 값을 계산하여 최단경로를 찾아내는 방법이고 다익스트라는 이미 주어진 가중치를 가지고 경로를 찾아내는 방법이다.

Copyright (C) 2016 DaeHyun, Hwang. all rights reserved.

hava

1 Comment

Graph

2016년 5월 3일 화요일

The revolution

Problem

Solving

Dijkstra Algorithm