플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 은 모든 정점 쌍 (i, j) 사이의 최단 거리를 구하는 DP 알고리즘. Robert W. Floyd (1962) 와 Stephen Warshall (1962) 이 독립적으로 발표. 음수 가중치 허용, 음수 사이클 검출 가능. 시간 복잡도 O(V^3).
문제 상황과 동기
그래프에서 모든 쌍 (i, j) 최단 거리를 구하고 싶다.
Dijkstra V번: V개 시작점에 대해 각각 O((V + E) log V). 총 O(V(V + E) log V) ≈ O(V^2 log V + VE log V). 간선 많으면 O(V^3 log V).
Floyd-Warshall: 항상 O(V^3). 코드 10줄. 음수 간선 OK, 구현 간단.
핵심 통찰: 중간 정점 k 를 거쳐 가는 경로 vs 안 거치는 경로 중 짧은 것 선택. k = 1..V 순회하면 모든 경로 고려.
시각화
핵심 아이디어
DP 상태: dist[i][j][k] = i 에서 j 로 가는데 중간 정점이 {1, 2, …, k} 부분집합인 최단 거리.
점화식:
dist[i][j][k] = min( dist[i][j][k-1], // k 안 거침 dist[i][k][k-1] + dist[k][j][k-1] // k 거침)
공간 최적화: k 차원 생략, 2D 배열 in-place 갱신 가능. dist[i][j] 를 직접 갱신.
for k = 1 to V: for i = 1 to V: for j = 1 to V: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
알고리즘
FloydWarshall(G): // 초기화 for i = 1 to V: for j = 1 to V: if i == j: dist[i][j] = 0 else if edge(i, j) exists: dist[i][j] = weight(i, j) else: dist[i][j] = ∞ // DP for k = 1 to V: // 중간 정점 k for i = 1 to V: // 시작점 i for j = 1 to V: // 도착점 j dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) // 음수 사이클 검출 for i = 1 to V: if dist[i][i] < 0: return "negative cycle" return dist
구현
// O(V^3) Floyd-Warshall#include <bits/stdc++.h>using namespace std;const long long INF = 1e18;int main() { int n, m; cin >> n >> m; vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF)); for (int i = 1; i <= n; i++) dist[i][i] = 0; for (int i = 0; i < m; i++) { int u, v; long long w; cin >> u >> v >> w; dist[u][v] = min(dist[u][v], w); // 중복 간선 처리 } // Floyd-Warshall for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); // 음수 사이클 검출 bool negCycle = false; for (int i = 1; i <= n; i++) { if (dist[i][i] < 0) { negCycle = true; break; } } if (negCycle) { cout << "NEGATIVE CYCLE\n"; } else { 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"; } }}
# O(V^3) Floyd-Warshallimport sysinput = sys.stdin.readlineINF = int(1e18)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] = 0for _ 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): for i in range(1, n + 1): for j in range(1, n + 1): if dist[i][k] != INF and dist[k][j] != INF: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])# 음수 사이클neg_cycle = any(dist[i][i] < 0 for i in range(1, n + 1))if neg_cycle: print("NEGATIVE CYCLE")else: for i in range(1, n + 1): print(' '.join(str(-1 if dist[i][j] == INF else dist[i][j]) for j in range(1, n + 1)))
// Floyd-Warshall O(V^3)import java.util.*;import java.io.*;public class Main { static final long INF = (long)1e18; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); long[][] dist = new long[n + 1][n + 1]; for (int i = 1; i <= n; i++) Arrays.fill(dist[i], INF); for (int i = 1; i <= n; i++) dist[i][i] = 0; for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); long w = Long.parseLong(st.nextToken()); dist[u][v] = Math.min(dist[u][v], w); } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); boolean negCycle = false; for (int i = 1; i <= n; i++) { if (dist[i][i] < 0) { negCycle = true; break; } } if (negCycle) { System.out.println("NEGATIVE CYCLE"); } else { StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) sb.append(dist[i][j] == INF ? -1 : dist[i][j]).append(' '); sb.append('\n'); } System.out.print(sb); } }}
stdin
4 71 2 31 4 52 3 23 4 14 1 22 4 43 1 6
결과
0 3 5 56 0 2 34 7 0 12 5 7 0
stdin
3 31 2 12 3 -33 1 1
결과
NEGATIVE CYCLE
복잡도
항목
값
시간
O(V^3)
공간
O(V^2)
음수 간선
✓
음수 사이클 검출
✓ (dist[i][i] < 0)
경로 복원
next[i][j] 배열 추가
V ≤ 300~500 정도면 실용. V > 1000 이면 Dijkstra V번이 더 빠를 수 있음 (희소 그래프).
경로 복원
next[i][j] = i 에서 j 로 가는 최단 경로의 다음 정점.
// 초기화for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j && dist[i][j] != INF) next[i][j] = j;// Floyd-Warshall 중 갱신for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; next[i][j] = next[i][k]; // i -> k 의 다음 정점 }// 경로 출력void printPath(int u, int v) { if (next[u][v] == -1) { cout << "No path\n"; return; } vector<int> path = {u}; while (u != v) { u = next[u][v]; path.push_back(u); } for (int p : path) cout << p << " ";}
💬 댓글