Floyd–Warshall 알고리즘

Floyd–Warshall 알고리즘

: Floyd–Warshall 알고리즘은 모든 정점 쌍 사이의 최단 경로(All-Pairs Shortest Paths, APSP) 를 구하는 알고리즘으로 아래와 같은 상황에서 주로 사용됨.

• 그래프의 모든 정점 쌍 (u, v)에 대해 최단 거리(또는 경로)를 구해야 할 때
• 음수 가중치(간선 가중치가 음수) 허용(단, 음의 사이클이 있으면 최단거리가 무한히 작아짐)
• 정점 수 V가 그리 크지 않을 때(시간복잡도 O(V^3))

* 한 번의 실행으로 모든 쌍의 최단 경로를 계산할 수 있기 때문에, 다익스트라(Dijkstra)나 벨만-포드(Bellman–Ford) 알고리즘과 달리 모든 정점 쌍에 대해 결과를 얻을 수 있음.

 

IDEA :

모든 정점(노드)을 중간 정점으로 허용하는 범위를 점차 넓혀가며,

그 중간 정점들만 사용해서 갈 수 있는 최단거리를 갱신해 나간다!

• k를 1부터 V까지 하나씩 증가시키면서,
• dist[i][j]를 현재 알고 있는 i에서 j로의 최단거리와
  i → k → j 경로(즉 dist[i][k] + dist[k][j])를 비교해서 더 작은 값을 선택한다.

k 루프를 바깥으로 빼는 것이 Floyd–Warshall의 핵심!

---

for k = 1..V:
  for i = 1..V:
    for j = 1..V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 

이때 dist[i][j]는 “중간 정점으로 {1..k} 만 허용할 때의 i→j 최단거리”를 의미함

---

시간/공간 복잡도

• 시간복잡도: O(V^3) (세 겹의 for문)
• 공간복잡도: O(V^2) (거리 행렬 dist), 경로 재구성용 next를 추가하면 O(V^2) 더 사용

따라서 정점 수가 수천 단위 이상이면 비용이 커짐. (정점 수가 400~1000이면 상황에 따라 괜찮기도 함)

---

음수 사이클 탐지

알고리즘을 수행한 뒤, 어떤 정점 v에 대해 dist[v][v] < 0 이면 음수 사이클이 존재한다는 뜻이다.
(정점 v에서 출발해서 v로 돌아오는 경로의 가중치 합이 음수라는 의미)

---

구현 팁 — 실전에서 자주 틀리는 점

• INF 더하기로 인한 오버플로우 주의
  • const int INF = 1e9; 같은 값을 쓰면 INF + INF가 int 범위를 넘어 음수로 바뀔 수 있음.
  • 해결: long long을 쓰고 INF를 충분히 큰 값(예: 1e15)으로 설정하거나, 덧셈 전에 == INF 체크를 한다.
  • 덧셈 전에 INF 체크이렇게 하면 애초에 유효하지 않은 경로를 더하지 않음.

if (dist[i][k] == INF || dist[k][j] == INF) continue;

 

• 경로 재구성(next matrix)
  • 최단거리뿐 아니라 실제 경로(노드 순서)도 필요하면 next[i][j]를 유지한다.
  • 갱신할 때 next[i][j] = next[i][k]로 설정하면 i→j 경로의 다음 정점을 알 수 있다.

---

예시

그래프 (정점 0,1,2):

• 0 → 1 (weight 3)
• 1 → 2 (weight 4)
• 0 → 2 (weight 10)

초기 거리 행렬은 다음과 같다 (INF는 경로가 없는 경우를 의미).

	0	1	2
0	0	3	10
1	INF	0	4
2	INF	INF	0

코드로 구현하면

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9; // 무한을 나타내는 큰 값

int main() {
    int n = 3; // 정점 개수
    vector<vector<int>> dist = {
        {0, 3, 10},
        {INF, 0, 4},
        {INF, INF, 0}
    };

    // Floyd–Warshall 알고리즘
    for (int k = 0; k < n; k++) {         // 거쳐가는 정점
        for (int i = 0; i < n; i++) {     // 출발 정점
            for (int j = 0; j < n; j++) { // 도착 정점
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 결과 출력
    cout << "최단 거리 행렬:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

k값을 하나씩 증가시키며 거리 행렬이 갱신되는 과정을 시각화하면

1. 초기 상태: 직접 연결된 간선만 반영됨
2. k=0: 정점 0을 거쳐가는 경로를 고려
3. k=1: 0 → 1 → 2 경로를 통해 0→2의 최단 거리 갱신 (10 → 7)
4. k=2: 더 이상 갱신 없음

 

출력결과

0 3 7
INF 0 4
INF INF 0

 

---

응용 문제

• 지하철/도로망에서 모든 역(정점) 쌍의 최단 시간 계산
• 네트워크 지연(latency) 분석
• 전이(close-closure) 기반 비용 계산
• 그래프에 음수 간선이 있고 모든 쌍 최단거리가 필요할 때

---

변형 및 최적화

• 경로 재구성: 위에 사용한 nxt 배열로 경로를 재구성 가능.
• 공간 최적화: dist를 2차원에서 1차원으로 최적화하기 어렵고 실무에선 잘 안 함(가독성/유지보수 문제).
• 병렬화: k 루프는 순차적이지만 i, j 루프는 병렬화 가능 → GPU/병렬 환경에서 가속 가능.
• Johnson’s algorithm: 희소 그래프(간선 수 << 정점^2)에서 모든 쌍 최단경로를 더 효율적으로 구할 수 있음 (O(V E log V)) — 음수 가중치도 처리 가능.