다익스트라 알고리즘과 그 활용

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

네델란드 컴퓨터 공학자 에츠허르 다익스트라(Edsger Wybe Dijkstra)가 만든 알고리즘으로 특정 지점로부터 나머지 지점까지의 최단거리를 모두 찾아주는 알고리즘이다.

알고리즘 수업의 필수코스로, CS를 전공했다면 반드시 배우게 된다. 음수 가중치가 있는 그래프에서는 사용 불가로, 이때는 벨만-포드 알고리즘을 사용해야 한다.

의사코드로 나타내 보면 아래와 같다. 자세한 설명은 이곳을 참고하자.

1
2
3
4
5
6
7
8
9
10
11
12
배열 cost를 INF값으로 초기화
PrioirtyQueue.Push(시작점, 0)
cost[시작점] = 0

while(Queue가 비어있지 않다면)
    현재점 = PrioirtyQueue.Pop()
    현재점이 이미 방문했다면, 방문 안한 점이 나올때까지 PrioirtyQueue.Pop()

    for (현재점에 인접한 모든 정점 X 에 대해)
        만약 ( cost[X] > cost[현재점] + 현재점에서 X까지 거리 ) 이면
            cost[X] = cost[현재점] + 현재점에서 X까지 거리
            PriorityQueue.Push(X, cost[X])

위의 의사코드를 C++으로 바꾸면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  for (int i = 1; i <= N; i++) {
    cost[i] = INF;
  }

  priorityQ.push({0, X});
  cost[X] = 0;

  while(!priorityQ.empty()) {
    P cur;
    do {
      cur = priorityQ.top();
      priorityQ.pop();
    } while(!priorityQ.empty() && visit[cur.second]);
    visit[cur.second] = 1;

    for (auto a : adj[cur.second]) {
      if (cost[a.second] > a.first + cur.first) {
        cost[a.second] = a.first + cur.first;
        priorityQ.push({cost[a.second], a.second});
      }
    }
  }

다익스트라의 활용 : 특정 정점으로 가는 최단거리 찾기

원래 다익스트라는 한점에서 모든 점으로 가는 최단거리를 찾는 알고리즘이지만, 역으로도 가능하다.

즉 모든 점에서 특정 정점으로 가는 최단거리를 찾을 수 있다. 원리는 간단한데, 모든 간선의 방향을 뒤집은 뒤 Dijkstra를 하면 된다.

아래 그림으로 보면 쉽게 이해가 될 것이다.

처음 그래프에서 모든 정점에서 1번 정점까지의 최단거리를 찾는 문제를 푼다고 가정하자.

간선의 방향을 모두 돌리고, 1번에서 다익스트라 알고리즘을 사용하자. 이때 구해진 최단거리는 반대방향 간선을 사용하므로, 1번으로 가는 최단거리를 모두 찾을 수 있다.