[알고리즘] 다익스트라 알고리즘에서 최단 경로 기록

이 글은 다익스트라 알고리즘에서 최단 경로를 기록하는 방법에 대해 정리하였습니다.

---

최단 경로를 기록하는 이유
✅ 다익스트라 알고리즘은 기본적으로 시작 노드에서 각 노드까지의 최소 비용(거리)을 구하는 데 최적화된 알고리즘이다. 하지만 실제 문제에서는 최단 거리 뿐만 아니라 어떤 경로로 이동했는지도 필요한 경우가 존재한다.
➡️ 지도 문제 : 도시 간 최단 거리와 구체적인 경로
➡️ 네트워크 경로 제어 : 최소 비용 라우팅에 사용
➡️ 최단 경로 관련 알고리즘 학습 : 문제 풀이 이해도 상승

🌐 기본 다익스트라 알고리즘은 아래 글 참고

https://devkuk.tistory.com/25

[알고리즘] 최단 경로 알고리즘 - 플러드 필(Flood Fill)과 다익스트라(Dijkstra)

---

단일 최단 경로 기록

최단 경로를 기록하는 가장 간단한 방법은 parent(혹은 path) 방식을 사용하는 것이다.

1. 각 노드마다 이 노드로 오기 위한 이전 노드(parent)를 하나만 기록
2. 다익스트라를 마친 후, 도착점에서 시작점까지 parent 배열을 역추적하면서 최단 경로를 복원

자료 구조

• vector<int> path;
  • path[u] : 정점 u에 도달하기 직전의 노드 (= u의 부모 노드)

---

알고리즘 구현 예시 (C++)

// dist[v] = 시작점에서 v까지의 최단 거리
// path[v] = v의 이전 노드
// 그래프는 graph[u] = { {v, cost}, ... } 형식 (인접 리스트)

void dijkstra(int start) {
  // 모든 노드까지의 거리 초기화
  dist.assign(n, INF);
  path.assign(n, -1);

  priority_queue<Node> pq;
  dist[start] = 0;
  pq.push({start, 0});

  while (!pq.empty()) {
    Node now = pq.top();
    pq.pop();

    // 이미 더 짧은 경로가 있으면 무시
    if (dist[now.node] < now.dist) continue;

    // 인접 노드 탐색
    for (int i = 0; i < graph[now.node].size(); i++) {
      Node edge = graph[now.node][i];

      int next = edge.node;
      int cost = edge.dist;
      int nextDist = now.dist + cost;

      // 더 짧은 경로 발견 시 갱신
      if (dist[next] > nextDist) {
        dist[next] = nextDist;
        path[next] = now.node;  // ‘이전 노드’ 기록
        pq.push({next, nextDist});
      }
    }
  }
}

// 최단 경로 복원
// 도착점 dest에서 시작해서 path[] 배열을 따라가며 복원
vector<int> getPath(int dest) {
  vector<int> route;
  if (dist[dest] == INF) {
    // 경로가 없는 경우
    return route;
  }
  for (int v = dest; v != -1; v = path[v]) {
    route.push_back(v);
  }
  reverse(route.begin(), route.end());
  return route;
}

➡️ 경로 기록의 핵심은 "이전 노드"를 기록하는 것

---

장단점

• 장점 : 구현이 간단하며, 최단 경로가 유일한 경우 강력하게 사용 가능
• 단점 : 최단 경로가 여러 개 존재할 때, 오직 한 경로만 복원이 가능

---

여러 개의 최단 경로 기록

최단 경로가 여러 개 존재할 때, 모든 최단 경로를 알아야 하는 경우가 존재 (ex. 백준 5719번 문제) ➡️ 각 노드로 도달 가능한 이전 노드들을 모두 기록

자료 구조

• vector<vector<int>> parent;
  • parent[v] : 정점 v로 가는 모든 최단 경로에 포함될 수 있는 이전 노드들의 집합

---

알고리즘 구현 예시 (C++)

void dijkstra(int start) {
  dist.assign(n, INF);
  parent.assign(n, vector<int>());  // 초기화

  priority_queue<Node> pq;
  dist[start] = 0;
  pq.push({start, 0});

  while (!pq.empty()) {
    Node now = pq.top();
    pq.pop();

    if (dist[now.node] < now.dist) continue;

    for (int i = 0; i < graph[now.node].size(); i++) {
      Node edge = graph[now.node][i];

      int next = edge.node;
      int cost = edge.dist;
      int nextDist = now.dist + cost;

      // 더 짧은 경로 발견
      if (dist[next] > nextDist) {
        dist[next] = nextDist;
        parent[next].clear();  // 기존 노드들 무효
        parent[next].push_back(now.node);
        pq.push({next, nextDist});
      }
      // 같은 거리로 도달할 수 있는 경로 발견
      else if (dist[next] == nextDist) {
        parent[next].push_back(now.node);
      }
    }
  }
}

➡️ 같은 거리로 해당 정점에 도달할 수 있는 "이전 노드"가 있다면 모두 기록

모든 최단 경로 역추적

✅ 모든 최단 경로를 역추적 할 때에는, 재귀를 통해 역추적을 한다.

// DFS or BFS를 통해 모든 경로를 탐색
void traceAllPaths(int v) {
  if (v == start) {
    // start 노드까지 도달했으므로, 경로 하나 완성
    return;
  }
  for (int i = 0; i < parent[v].size(); i++) {
    int prev = parent[v][i];
    // prev -> v 간선은 최단 경로 중 하나
    traceAllPaths(prev);
  }
}

---

장단점

• 장점 : 모든 최단 경로를 얻을 수 있어, 여러 경로를 처리하거나 간선 혹은 노드를 제거할 때 활용 가능
• 단점 : 구현과 관리가 다소 복잡하여 최단 경로의 수가 매우 많을 경우, 시간 및 메모리 사용량이 급증할 수 있음

---

기타 팁 & 주의 사항

• paht[v] = u vs parent[v].push_back(u)
  • 문제 조건에 따라 선택하여 사용 (최단 경로 한 개 : path[v] = u 사용 / 최단 경로 여러 개 : parent[v].push_back(u) 사용)
• 메모리 최적화
  • 최단 경로 역추적이 필요 없는 경우 ➡️ path 혹은 parent를 굳이 생성하지 않아도 됨
• 초기값 설정
  • path[v] = -1 (존재하지 않는 노드)
  • dist[v] = INT_MAX or dist[v] = INF
  • parent[v] = {} (빈 리스트)
• 시작 노드의 이전 노드
  • 일반적으로 path[start] = -1로 설정
• 역추적 순서
  • 보통 도착점에서 시작하여 path[]를 따라가며 역추적 (for (int i = dest; i != -1; i = path[i]))
  • 모든 경로를 원한다면 DFS(재귀) 또는 BFS(큐)를 활용해 parent[v] 탐색
• 무한 루프 방지
  • parent를 사용할 때, 원치 않는 사이클이 있지는 않는지 확인
  • 다익스트라 특성 상 음수 가중치가 없다면 일반적으로 사이클 문제가 발생하지 않음