플로이드-워셜

어떤 문제를 푸는가

모든 정점 쌍 \((i, j)\) 사이의 최단 거리를 한꺼번에 구합니다. 정점이 적고
(\(V \le 400\) 정도) 쌍 전부의 거리가 필요할 때, 한 줄짜리 삼중 루프로 끝나는
이 방법이 압도적으로 편합니다. 음수 간선도 허용합니다(음수 사이클만 없으면).

핵심 아이디어 — 경유 정점을 하나씩 허용

dist[i][j]를 "정점 \(i\)에서 \(j\)로 가는 최단 거리"로 두고, 경유해도 되는
중간 정점의 집합을 \(\{1\}, \{1,2\}, \dots\) 처럼 점점 넓혀 갑니다.

\(k\)번째 정점까지 경유를 허용했을 때의 거리를 \(dist_k[i][j]\)라 하면,

$$ dist_k[i][j] = \min\bigl(dist_{k-1}[i][j],\ dist_{k-1}[i][k] + dist_{k-1}[k][j]\bigr) $$

즉 "\(k\)를 거치지 않는 기존 경로" vs "\(i \to k \to j\)로 \(k\)를 거치는 경로"
중 작은 쪽입니다.

왜 옳은가

\(i\)에서 \(j\)로 가는 임의의 최단 경로를 봅니다. 그 경로가 사용하는 중간 정점들
중 번호가 가장 큰 것 을 \(k\)라 하면, 경로는 "\(i \to k\) (중간 정점 번호 모두
\()" + "\(k \to j\) (역시 모두 \()"로 쪼개집니다. 두 조각은 정확히
\(dist_{k-1}\)가 다루는 경우이므로, \(k\)를 마지막으로 허용하는 단계에서 이 경로가
포착됩니다. 모든 \(k\)를 차례로 허용하면 모든 최단 경로가 고려됩니다.

여기서 \(k\) 루프가 가장 바깥 이어야 한다는 점이 절대적으로 중요합니다.

1차원으로 in-place 갱신해도 되는 이유

\(k\) 단계에서 dist[i][k]와 dist[k][j]는 이번 단계에 갱신되더라도 값이
변하지 않습니다 (dist[k][k] = 0이므로). 그래서 배열 한 장으로 덮어써도
정확합니다.

복잡도

\(V = 400\)이면 \(6.4 \times 10^7\)로 충분히 빠릅니다. \(V\)가 수천을 넘으면
못 씁니다 — 그때는 각 정점마다 다익스트라(\(O(V \cdot E \log V)\))를 고려합니다.

음수 사이클 탐지

플로이드-워셜 후 어떤 정점 \(i\)에 대해 dist[i][i] < 0이면, \(i\)가 음수
사이클 위에 있다는 뜻입니다. 자기 자신으로 돌아오는 비용이 음수일 수 없기
때문입니다. 다음 강의에서 구현과 응용을 봅니다.

표준 구현 (C++)

루프 순서 k, i, j 를 절대 어기지 마세요.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int n, m; cin >> n >> m;
    vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;   // 자기 자신은 0

    for (int e = 0; e < m; e++) {
        int u, v; ll w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);            // 중복 간선은 최솟값
    }

    for (int k = 1; k <= n; k++)                     // 경유 정점이 바깥
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] == INF) continue;        // 가지치기 + 오버플로 방지
            for (int j = 1; j <= n; j++)
                if (dist[k][j] != INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cout << (dist[i][j] == INF ? -1 : dist[i][j]) << ' ';
        cout << '\n';
    }
}

if (dist[i][k] == INF) continue;는 도달 불가 정점을 통한 잘못된 갱신을
막고, 안쪽 루프도 통째로 건너뛰어 상수배 속도까지 챙깁니다.

파이썬 구현

import sys
input = sys.stdin.readline
INF = float('inf')

n, m = map(int, input().split())
dist = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    dist[i][i] = 0
for _ in range(m):
    u, v, w = map(int, input().split())
    dist[u][v] = min(dist[u][v], w)

for k in range(1, n + 1):
    dk = dist[k]
    for i in range(1, n + 1):
        dik = dist[i][k]
        if dik == INF:
            continue
        di = dist[i]
        for j in range(1, n + 1):
            nd = dik + dk[j]
            if nd < di[j]:
                di[j] = nd

파이썬 \(O(V^3)\)는 상수가 커서 \(V\)가 수백이면 위처럼 지역 변수로 캐싱해
가속해야 시간 안에 듭니다.

흔한 함정

• 루프 순서 — i, j, k나 i, k, j로 잘못 짜면 틀린 답이 나옵니다.
  반드시 k가 가장 바깥. 이 단원에서 단연 1순위 실수입니다.
• INF 덧셈 오버플로 — 도달 불가를 더하지 않도록 위처럼 검사.
• 자기 루프 초기화 — dist[i][i] = 0을 잊으면 안 됩니다.
• 중복 간선 — 같은 \((u, v)\)가 여러 번 들어오면 최솟값만 남깁니다.

응용 패턴

• 경유 가능성(도달성) — min/+ 대신 or/and로 바꾸면 이행적 폐포
  (Floyd-Warshall reachability)를 \(O(V^3)\)에 구합니다.
• 최소 사이클(가장 짧은 사이클 길이) — 갱신 도중 \(dist[i][k]+dist[k][j]+w(j,i)\)
  형태로 사이클 길이를 추적.
• 경로 복원 — nxt[i][j]에 "i 다음 정점"을 저장해 경로를 복원.
• 병목 경로(최소 최대 간선) — +를 max로 바꾸면 미니맥스 경로.

작은 그래프에서 "모든 쌍"이 필요하면 가장 먼저 떠올릴 도구입니다. 짧지만
루프 순서 하나에 정답이 걸려 있다는 점을 늘 기억하세요.

출제 신호

• "모든 쌍 (또는 여러 출발점-도착점 조합)의 최단 거리" + \(V \le 500\).
  이 정점 수 제한이 사실상 정답 공개입니다 — \(O(V^3) = 1.25 \times 10^8\)이
  허용된다는 뜻이니까요.
• "임의의 두 도시 사이", "어느 정점에서 출발해도", "거쳐서 가는 경로 포함"
• 거리 외의 변장: "\(i\)에서 \(j\)로 갈 수 있는가"(도달성 — 경로 행렬),
  "두 사람 사이의 비교 관계를 몇 쌍이나 알 수 있는가"(순서 폐포),
  "각 정점에서 가장 먼 정점", "그래프의 지름"
• 질의 수가 매우 많아(\(Q \ge 10^5\)) 매번 다익스트라를 돌릴 수 없을 때의
  사전 계산용

\(V\)가 1000을 넘으면 \(V^3\)이 \(10^9\)를 넘으므로 정점별 다익스트라
(\(O(V E \log V)\))와 비교해 선택해야 합니다.

풀이 결정 절차

1. \(V^3\)을 계산해 시간 안인지 확인합니다 (\(V \le 500\) 안전, \(V \approx 800\) 경계).
2. 답이 거리인가, 도달성인가, 경로 자체인가 — 도달성이면 dist 대신 bool,
   경로 복원이면 nxt[i][j](또는 경유점) 테이블을 함께 갱신합니다.
3. 초기화를 설계합니다 — d[i][i] = 0, 간선 있으면 d[u][v] = w
   (중복 간선은 min), 나머지 INF.
4. 음수 간선은 허용되지만 음수 사이클이 있으면 결과가 무의미해집니다 —
   판정이 필요하면 실행 후 d[i][i] < 0인 \(i\)를 찾습니다.

자주 하는 실수

• 루프 순서 — 경유점 \(k\)가 반드시 가장 바깥이어야 합니다. 점화식
  \(d_k[i][j] = \min(d_{k-1}[i][j],\ d_{k-1}[i][k] + d_{k-1}[k][j])\)에서 \(k\)는
  "여기까지의 경유점 허용 집합"이라는 DP 차원이기 때문입니다. \(i\)나 \(j\)를
  바깥에 두면 일부 경로가 누락됩니다.

for (int k = 1; k <= n; k++)          // 경유점이 최외곽 — 순서가 본질
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

• INF + INF 오버플로 — int에 INF = 2e9 근처를 쓰면 d[i][k]+d[k][j]가
  넘칩니다. INF = 1e9처럼 두 배 해도 안전한 값을 쓰거나, 이완 전에
  if (d[i][k] == INF || d[k][j] == INF) continue;를 넣으세요.
• 중복 간선을 마지막 값으로 덮어씀 — 입력에 같은 (u, v) 간선이 여러 번
  오면 d[u][v] = min(d[u][v], w)로 받아야 합니다.
• d[i][i] = 0 누락 — 자기 자신으로의 거리가 INF로 남아 경유 계산이 깨집니다.
• 경로 복원 테이블 갱신 누락 — 거리를 갱신할 때만 nxt[i][j] = nxt[i][k]로
  같이 갱신해야 합니다. 거리 따로 경로 따로 만들면 어긋납니다.

연습 방법

사이드바 연습 목록의 기본 모든-쌍 거리 문제로 3중 루프와 초기화를 몸에
익힌 뒤, 도달성(경로 행렬) 변형과 경로 복원 문제로 확장하세요. "정점 수가
몇이면 플로이드인가"라는 감각(\(\le 500\))을 기르는 것이 이 단원의 절반입니다 —
문제를 보면 제약부터 확인하는 습관을 들이세요. 태그된 문제 3문제 이상
해결 시 마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.