Floyd-Warshall: Dynamic Programming으로 모든 쌍 최단 경로

Floyd-Warshall는 Dynamic Programming으로 모든 Vertex Pair 사이의 최단 거리를 계산합니다.

핵심 식:

dist[i][j] =
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

각 k를 중간 정점으로 사용할 때 경로가 더 짧아지는지 확인합니다.

초기화

dist[i][i] = 0

직접 Edge가 없으면 Infinity를 사용합니다.

음수 Edge

Negative Edge를 지원합니다.

실행 후:

dist[i][i] < 0

이면 Negative Cycle이 존재합니다.

Path Reconstruction

next[i][j] Matrix를 유지하면 실제 경로도 복원할 수 있습니다.

Reachability

min/+ 대신 OR/AND를 사용하면 Transitive Closure를 계산할 수 있습니다.

비교

Floyd-Warshall:

All Pairs
O(V³)

큰 Sparse Graph에서는 반복 Dijkstra나 Johnson이 더 적합할 수 있습니다.

활용

• Routing Matrix
• Logistics
• Network Latency
• Reachability
• Dependency Analysis

복잡도

시간: O(V³)
공간: O(V²)

정리

모든 쌍의 Shortest Path가 필요하고 Vertex 수가 중간 규모일 때 Floyd-Warshall이 매우 간결한 선택입니다.