[Algorithm] 다익스트라 알고리즘(Dijkstra's Algorithm)

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

다익스트라 알고리즘은 시작 정점에서 모든 나머지 정점까지의 최단거리(cost)를 구하는 알고리즘 중 하나다. 주로 주어진 두 노드 사이의 최단거리(cost)를 구하는 데 유용하게 사용된다.

 

 

다익스트라 알고리즘 특징

1. 정점의 개수가 V, 간선의 개수를 E일 때 O(ElogV)의 시간복잡도를 가진다.
2. 모든 거리(cost)가 음수가 아닐 때만 사용할 수 있다.
3. 우선순위 큐(최소 힙)를 사용한다.

 

다익스트라 알고리즘 작동 방식

다익스트라 알고리즘 사진 (출처: 위키피디아)

1. 아직 방문하지 않은 정점들 중 거리(cost)가 가장 작은 정점을 하나 선택해 방문한다.
2. 해당 정점에 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.
3. 모든 정점을 방문하면 종료한다.

1번 과정을 위해 우선순위 큐(최소 힙)가 사용된다. pair가 들어있으면 first를 우선해서 정렬하는 우선순위 큐의 특징에 따라 우선순위 큐에 dist[i]와 정점의 번호 v를 담는다. dist 배열은 시작 정점부터의 최단거리를 저장한다. top의 정점을 이미 방문한 경우는 그냥 pop하고 만족하는 데이터가 나올 때까지 뽑으면 된다. 그리고 위 과정을 진행하면 된다.

 

과정이 끝난 후 dist[i]의 값은 시작점으로부터 i번 정점까지 실제 최단거리가 된다. 그리고 이미 방문된 점의 dist값은 이미 최단거리고 절대 바뀌지 않는다. 이는 다음과 같이 증명할 수 있다.

 

임의의 아직 방문하지 않았고 dist 값이 가장 작은 정점 u에 대해, 만약 실제 최단 거리보다 dist[u]가 크다면 dist[u]는 임의의 아직 방문하지 않은 정점 v에 의해 dist[u] = dist[v] + d[v][u]로 갱신될 수 있다. d는 정점 v로부터 u로 이동하는 거리다. 하지만 이를 만족하려면 dist[u] > dist[v] 여야 하는데 u는 방문하지 않은 정점 중 dist값이 가장 작은 정점이므로 이를 만족하는 v는 존재할 수 없다. 따라서 어느 정점 u를 방문한 순간, dist[u]는 최단거리가 된다.

 

그리고 위 증명을 위한 조건이 d는 0 이상이다. d가 음수인 경우엔 벨만 포드 알고리즘이라는 다른 알고리즘을 사용해야 한다.

 

 

예제를 통한 구현

https://www.acmicpc.net/problem/1753

1753번: 최단경로

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int V, E, K;
  cin >> V >> E >> K;

  // 간선
  vector<pair<int, int>> graph[20001]; // [정점][다음 정점, 거리]
  while (E--) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back({v, w});
  }

  // 다익스트라
  vector<int> dist(20001, INT_MAX), visited(20001, 0);
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  dist[K] = 0;          // 시작점 거리 0
  pq.push({0, K});      // 시작점만 pq에 추가
  while (!pq.empty()) { // pq가 비면 종료
    int curr;
    do {
      curr = pq.top().second;
      pq.pop();
    } while (!pq.empty() && visited[curr]); // curr이 방문한 정점이면 무시
    // 더 이상 방문할 수 있는 정점이 없으면 종료
    if (visited[curr])
      break;

    visited[curr] = 1; // 방문처리

    for (auto &p : graph[curr]) {
      int next = p.first, d = p.second;
      // 거리가 갱신될 경우 pq에 추가
      if (dist[next] > dist[curr] + d) {
        dist[next] = dist[curr] + d;
        pq.push({dist[next], next});
      }
    }
  }

  // 출력
  for (int i = 1; i <= V; i++)
    if (dist[i] == INT_MAX)
      cout << "INF\n";
    else
      cout << dist[i] << '\n';

  return 0;
}