단원 25 — 플로이드-워셜 (Floyd-Warshall)

dist[i][j][k] = 노드 1~k 만 경유 가능할 때, i→j 최단 거리

점화식:
dist[i][j][k] = min(
    dist[i][j][k-1],           ← k 를 경유하지 않음
    dist[i][k][k-1] + dist[k][j][k-1]  ← k 를 경유함
)

k 차원을 제거(공간 최적화):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# 초기화
for i in range(V):
    for j in range(V):
        dist[i][j] = INF
    dist[i][i] = 0          # 자기 자신 거리 = 0
for u, v, w in edges:
    dist[u][v] = min(dist[u][v], w)

# 메인 루프 (k = 경유 노드)
for k in range(V):          # 순서 중요!
    for i in range(V):
        for j in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

그래프 (방향, 4개 노드 0~3):

  0 ──3── 1
  │ \     │
  7   2   1
  │     \ │
  3 ──1── 2

간선: 0→1:3, 0→2:2, 0→3:7, 1→2:1, 2→3:1

초기 dist 행렬 (INF 생략):
     0    1    2    3
0  [ 0    3    2    7  ]
1  [INF   0    1   INF ]
2  [INF  INF   0    1  ]
3  [INF  INF  INF   0  ]

k=0 경유 후 (0을 거치는 경로 추가):
     0    1    2    3
0  [ 0    3    2    7  ]
1  [INF   0    1   INF ]
2  [INF  INF   0    1  ]
3  [INF  INF  INF   0  ]
(변화 없음 — 0→?→1 경로가 더 길기 때문)

k=1 경유 후:
     0    1    2    3
0  [ 0    3    2    7  ]  (0→1→2 = 4 > 기존 2, 변화 없음)
1  [INF   0    1   INF ]
2  [INF  INF   0    1  ]
3  [INF  INF  INF   0  ]

k=2 경유 후:
     0    1    2    3
0  [ 0    3    2    3  ]  (0→2→3 = 3 < 7 ← 갱신!)
1  [INF   0    1    2  ]  (1→2→3 = 2 ← 갱신!)
2  [INF  INF   0    1  ]
3  [INF  INF  INF   0  ]

k=3 경유 후:
(3을 경유해도 단축되는 경로 없음)
최종 dist:
0→0=0, 0→1=3, 0→2=2, 0→3=3
1→2=1, 1→3=2
2→3=1

python src/01_floyd_warshall.py
python src/02_floyd_path.py
python src/03_negative_cycle.py
python src/04_transitive_closure.py

플로이드-워셜 요약
━━━━━━━━━━━━━━━━━━━━━
문제 유형   : 모든 쌍 최단 경로
시간 복잡도 : O(V³)
공간 복잡도 : O(V²)
음수 간선   : 허용 (사이클 없을 때)
음수 사이클 : dist[i][i] < 0 으로 탐지
경로 복원   : next[V][V] 행렬
도달 가능성 : bool 행렬로 응용