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

다익스트라 알고리즘

다익스트라 알고리즘은 그래프 내 특정 정점에서 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다.

인공위성 GPS와 같은 다양한 분야에서 많이 사용된다.

그래프의 간선에 음수 가중치가 있다면 사용할 수 없지만, 현실에는 일반적으로 음수 가중치가 존재하지 않으므로 다익스트라가 효과적이다.

간선 가중치가 음수인 그래프에서는 ~벨만-포드 알고리즘~ 같은 다른 방법을 사용해야 한다.

---

구현하기 (C++)

vector<long long> dijkstra(int start) {
  vector<long long> dist(n + 1, LLONG_MAX);
  dist[start] = 0;
  priority_queue<pair<int, int>> pq;
  pq.push({0, start});

  while (!pq.empty()) {
    int cost = -pq.top().first;
    int cur = pq.top().second;
    pq.pop();

    if (dist[cur] < cost) continue;

    for (int i = 0; i < node[cur].size(); i++) {
      int next = node[cur][i].first;
      int nextCost = node[cur][i].second + cost;

      if (dist[next] > nextCost) {
        dist[next] = nextCost;
        pq.push({-nextCost, next});
      }
    }
  }

  return dist;
}

~dijkstra~ 함수를 호출하기 전에 이미 ~node~에 그래프의 정보가 들어있어야 한다.

node[i]에는 { w, j } 쌍이 들어있고. 이는 i에서 j로 가는 간선의 가중치가 w임을 의미한다.

 

정의 및 초기화

vector<long long> dijkstra(int start) {
  vector<long long> dist(n + 1, LLONG_MAX); // 시작 노드로부터 각 노드까지의 최단 거리를 저장하는 벡터, 초기값은 LLONG_MAX로 설정
  dist[start] = 0; // 시작 노드의 거리는 0으로 설정
  priority_queue<pair<int, int>> pq; // 우선순위 큐: {비용, 노드 번호} 형태
  pq.push({0, start}); // 시작 노드를 큐에 추가
}

• ~dist~: 각 노드의 최단 거리를 저장하며, 초기값으로 무한대를 나타내는 LLONG_MAX를 사용.
• ~priority_queue~: 최단 거리를 빠르게 추출하기 위해 사용되는 자료구조.
  • 비용을 음수로 저장하여 최소 힙처럼 동작하게 만듦(기본적으로 C++의 priority_queue는 최대 힙).

 

우선순위 큐를 이용한 탐색

while (!pq.empty()) {
  int cost = -pq.top().first; // 현재 노드까지의 비용
  int cur = pq.top().second; // 현재 노드
  pq.pop();

  if (dist[cur] < cost) continue; // 이미 처리된 노드는 건너뜀
}

• 현재 노드(cur)와 해당 노드까지의 비용(cost)을 추출.
• 이미 더 작은 비용으로 처리된 적이 있는 경우 현재 노드는 무시.

 

인접 노드 탐색

for (int i = 0; i < node[cur].size(); i++) {
  int next = node[cur][i].first; // 다음 노드
  int nextCost = node[cur][i].second + cost; // 다음 노드까지의 비용

  if (dist[next] > nextCost) { // 더 작은 비용으로 도달 가능하면 갱신
    dist[next] = nextCost;
    pq.push({-nextCost, next}); // 다음 노드로 가는 경로를 큐에 추가
  }
}

• 현재 노드 cur에 연결된 모든 인접 노드 next를 탐색.
• 새로운 비용 nextCost가 기존 비용보다 작으면:
  1. dist[next]를 갱신.
  2. next와 갱신된 비용을 우선순위 큐에 추가.

 

반환

return dist;

• 모든 노드까지의 최단 거리가 저장된 dist 벡터를 반환.