다익스트라 알고리즘은 이렇게 쓰는 게 맞다!

최단 경로 알고리즘 문제를 풀기 위해, 처음 다익스트라 알고리즘을 공부하면서 너무 헷갈렸다.

개념 자체는 우선순위 큐를 사용한 BFS이기 때문에 하나도 어렵지 않다.

근데 왜 헷갈렸느냐? 인터넷에는 수많은 버전의 제각기 다른 다익스트라 알고리즘들이 있었다.

알고리즘 문제를 푼 사람들의 코드를 보면, 다들 다익스트라의 개념은 맞지만 조금씩 다르게 구현해서 쓰고 있었다.

그 중에는 쓸데없이 성능상 저하가 있는 코드도 있었고,

이런 특수한 케이스에서는 틀릴 것 같은데? 싶은 코드도 있었다.

 

---

 

따라서 나는 알고리즘 문제를 풀기에 가장 "적합한" 다익스트라 알고리즘의 코드를 만들었다.

(내 머리에서 가장 적합하다고 생각한 것이기 때문에, 이보다 더 좋은 구현이 있을 수도 있지만)

 

다음 블록에 내 다익스트라 알고리즘의 코드를 주석으로 설명해서 정리하겠다.

struct Node {
  int node; int weight;
  Node(int _node, int _weight) : node(_node), weight(_weight) {}
  
   // c++의 우선순위 큐는 max heap 이기 때문에,
   // 가중치가 낮은 것부터 차례로 꺼내기 위한 연산자 오버로딩.
  bool operator<(const Node &rhs) const {
    return weight > rhs.weight;
  }
};

void daijkstra(Node start) {
  for (int i = 1; i <= n; ++i) dist[i] = INT32_MAX;
  priority_queue<Node> pq;

  dist[start.node] = start.weight;
  pq.push(start);
  
  // 다익스트라 알고리즘 시작
  while (!pq.empty()) {
    Node current = pq.top(); pq.pop();
    
    // dist 에 기록된 최단거리보다 현재 노드까지의 거리가 더 큰 경우,
    // 검사할 필요가 없음.
    if (dist[current.node] < current.weight) continue; // 1번
    
    for (int i = 0; i < graph[current.node].size(); ++i) {
      Node next = graph[current.node][i];
      
      // 마찬가지로 dist 에 기록된 다음 노드까지의 최단거리보다
      // 현재 노드까지의 최단거리 + 다음 노드의 가중치가 더 큰 경우 continue
      if (dist[next.node] <= next.weight + current.weight) continue; // 2번
      
      dist[next.node] = next.weight + current.weight;
      pq.push(Node(next.node, next.weight + current.weight));
    }
  }
}

 

---

 

처음에 약간 헷갈렸던 점

• 위의 코드에 주석으로 단 번호 1번 라인과 2번 라인을 보면, 사실 완전히 같은 논리임을 알 수 있다. 2번 조건을 통해 삽입된 노드가, 다음 while 루프에서 같은 값으로 그대로 꺼내지기 때문. 그렇다면 왜 굳이 2번이나 최단거리를 비교하는 것일까?

이에 대한 답은 이렇다.

현재 노드의 최단거리를 비교하는 로직을 거친 후, for 루프를 돌 때, 현재 노드의 모든 인접 노드에 대해 탐색한다. 그리고 우선순위 큐의 순서에 따라서, 가중치가 낮은 다음 노드를 또 탐색하고, 그 다음 노드의 인접한 노드 중에 가중치가 낮은 노드를 또 우선적으로 탐색한다.

 

따라서, 우선순위 큐에 노드를 삽입했을 시점의 그 노드까지의 최단거리와, 가중치가 낮은 노드들을 먼저 다 검사한 후에 해당 노드가 우선순위 큐에서 꺼내졌을 시점의 최단거리는 다를 수 있다는 것!

 

 

---

 

참고로 위의 다익스트라 알고리즘 구현은 음의 가중치를 가진 간선이 있어도 최단거리를 보장받을 수 있다.

하지만 그럼에도 음의 가중치를 가진 간선이 있을 때 벨만-포드 알고리즘을 사용해야 하는 이유는,

음의 가중치를 가진 간선의 사이클을 감지할 수 없기 때문이다.

따라서 그런 사이클이 그래프에 존재한다면, 모든 노드까지의 최단거리는 모두 -INF가 된다.

(음의 가중치의 사이클을 무한히 돈 다음에 목적지에 도달하면 되기 때문)