최단 경로 알고리즘 (BFS, 다익스트라, 벨만 포드, 플로이드 워셜)

최단 경로 문제를 풀 때, 어떤 알고리즘을 선택해야하는지 정리하기 위한 글이다.

BFS

2차원 배열에서 최단 경로를 구해야하는 문제를 볼때마다 BFS를 사용해서 문제를 풀었다.

항상 최단 경로 문제를 풀 때마다 이를 활용해서 문제를 풀다가 정답을 구할 수 없는 경우가 발생했다.

바로, 가중치가 있는 경우이다.

위와 같은 그래프가 있을 때, a에서 b로 가는 최단 거리를 구하려고 한다.

BFS방식을 사용한다면 a와 연결된 b, d노드로 가게 될 것이고, b노드를 발견한 즉시 탐색을 종료하게 된다.

a → b 경로는 12의 거리가 소요되고, a → d → c → b 경로는 9의 거리가 소요되지만 먼저 방문한 노드가 우선시 되는 것이다.

위의 이유로 일찍 만난 노드가 가장 우선시 되어 종료될 수 있는 경우

1. 가중치가 없는 경우
2. 가중치가 동일한 경우

조건을 만족할 때 BFS 알고리즘을 사용한다.

---

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

다익스트라 알고리즘은 BFS의 가중치 문제를 해결한 알고리즘이다.

BFS알고리즘을 사용할 때와 달리 우선순위 큐에 가중치도 함께 넣어 정렬한다.

알고리즘 구조

1. 시작 정점부터 모든 정점까지의 최단거리를 INF로 초기화 한다.
   1. dist[V] = INF;
2. 시작 정점 설정
   1. priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 오름차순
   2. dist[start] = 0;
   3. pq.push({start, 0});
3. 우선 순위 큐에서 가중치가 가장 작은 값 꺼내기
   1. int cost = pq.top().first; // 현재 노드의 가중치
   2. int cur = pq.top().second; // 현재 노드
4. 지금 꺼낸 것보다 기존 경로가 더 짧다면 무시
   1. if(dist[cur] < cost) continue;
5. 연결된 정점을 모두 검사

   1. for(int i = 0; i < adj[cur].size(); i++) {
        int next = adj[cur][i].first; // 인접 노드
        int nextCost = cost + adj[cur][i].second; // 현재 가중치에 다음 인접노드 가중치 더하기
        if(dist[next] > nextCost) { // 더 짧은 경로 발견 시 dist[]갱신하고 우선순위 큐에 넣기
            dist[next] = nextCodst; 
            pq.push(nextCost, next);
          }
      }

6. 결국 dist배열에는 시작 정점부터 각 정점까지의 최단거리가 저장된다.

---

벨만 포드 알고리즘(Bellman Ford) 알고리즘

만약 가중치가 음수인 간선이 있다면 어떻게 될까? 다익스트라의 경우 최단 경로를 알 수 없다.

벨만 포드 알고리즘은 특정 정점에서의 최단 경로를 찾을 수 있다는 점은 다익스트라 알고리즘과 동일하지만, 음수 간선이 있는 경우에도 최단 경로를 찾을 수 있다!

음수 사이클 판정

게다가 음수 사이클이 있어 최단 경로가 제대로 정의되지 않는 경우 이를 알려준다.

정점이 V개 있을 때, 모든 최단 경로를 V-1번의 탐색으로 판단할 수 있다. 하지만 음수 사이클이 있는 경우에는 V번째 탐색 시에도 더 낮은 비용의 경로를 발견하게 된다.

알고리즘 원리

이 알고리즘은 시작점에서 각 정점까지의 최소비용을 예측한 뒤, 실제 최단 경로 사이의 오차를 반복적으로 줄여나간다. 한 번에 한 노드씩 확장해나가는 다익스트라 알고리즘과의 차이가 이것이다~!

알고리즘 구조

1. 시작 정점부터 모든 정점까지의 최단거리를 INF로 초기화 한다.
   1. dist[V] = INF;
2. 시작 정점 설정
   1. dist[start] = 0;
3. 정점개수 V번 순회

   1. bool updated;
      for (int v = 0; v < V; v++) { // V번 탐색
          updated = false;
          for (int cur = 1; cur <= V; cur++) {
              for (int j = 0; j < adj[cur].size(); j++) {
                  int next = adj[cur][j].first;
                  int nextCost = adj[cur][j].second;
      			if (dist[cur] == INF) continue; // 아직 연결된 경로가 없는 정점은 업데이트하지 않음
                  if (dist[next] > dist[cur] + nextCost) { // 더 가까운 경로 발견 시
                      dist[next] = dist[cur] + nextCost;
                      updated = true;
                  }
              }
          }
          if(!updated) break; // 업데이트되지 않았다면 종료
      }
      if(updated) // 만약 V번 모두 업데이트되었다면 음수 사이클이 존재한다

4. V번 반복 전에 업데이트가 끝난다면 결국 dist배열에는 시작 정점부터 각 정점까지의 최단거리가 저장된다.

---

플로이드 워셜(Floyd Warshall) 알고리즘

다익스트라나 벨만 포드 알고리즘은 한 시작점에서 다른 모든 정점까지의 최단 경로를 알 수 있었다. 그렇다면 모든 정점에 대해 다른 모든 정점 사이의 최단 거리를 구해야 한다면 어떻게 해야할까?

간단하게는 각 정점을 시작으로 다익스트라나 벨만 포드 알고리즘을 모두 실행하면 된다. 하지만 이는 많은 연산이 필요할 것이다.

알고리즘 원리

두 정점 u, v 사이의 경로를 찾아보자.

경유할 수 있는 모든 점을 x라고 하면 x를 경유할 수도 있고, 경유하지 않을 수도 있다.

1. 정점 x를 경유하지 않는다면? x를 제외한 점만을 경유한다.
2. 정점 x를 경유한다면? 전체 경로의 구성은 다음과 같다.
   1. u에서 x로 가는 경로
   2. x에서 v로 가는 경로그리고 이 두가지 경로는 최단 경로들이어야 한다.

결국, 위 두 가지 방법 중 더 짧은 경로가 최단 경로가 된다.

알고리즘 구조

for (int i = 0; i < V; i++) { adj[i][i] = 0; } // 자신으로 이동하는 비용 0
for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            // k를 경유하지 않는 경우, 경유하는 경우 비용 비교
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); 
        }
    }
}