핵심 정리
| 조건 | 내용 |
|---|---|
| 대상 | 모든 정점 쌍 최단 거리 |
| 시간 | O(V³) |
| 공간 | O(V²) |
| 음수 간선 | 가능 |
| 음수 사이클 | dist[i, i] < 0이면 존재 |
csharp
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] == INF || dist[k, j] == INF) continue;
dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
}
}
}구조
Floyd-Warshall은 k번 정점을 경유지로 사용할 수 있을 때 최단 거리가 줄어드는지 확인합니다. 핵심은 반복 순서입니다. k가 가장 바깥에 있어야 “0..k까지의 정점만 중간 경유지로 허용한다”는 DP 의미가 유지됩니다.
text
dist[i, j] = i에서 j로 바로 가는 거리
dist[i, j] = min(dist[i, j], dist[i, k] + dist[k, j])초기화는 결과를 크게 좌우합니다. 자기 자신은 0, 간선이 없으면 INF, 여러 간선이 있으면 더 작은 비용을 저장합니다.
csharp
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dist[i, j] = i == j ? 0 : INF;
}
}
foreach ((int from, int to, long cost) in edges)
{
dist[from, to] = Math.Min(dist[from, to], cost);
}선택 기준
| 문제 조건 | 판단 |
|---|---|
| 모든 출발점과 도착점의 최단 거리 필요 | Floyd-Warshall |
| 정점 수가 작고 질의가 많음 | Floyd-Warshall |
| 정점 수가 크고 시작점 하나만 필요 | Dijkstra 또는 Bellman-Ford |
| 간선 비용이 모두 1 | 각 시작점 BFS 검토 |
| 도달 가능성만 필요 | transitive closure로 변형 가능 |
정점 수가 500이면 약 1억 2500만 번의 갱신이 필요합니다. 언어와 시간 제한에 따라 가능할 수 있지만, 정점 수가 1000을 넘으면 대부분 부담이 커집니다.
주의할 점
INF + cost를 계산하면 overflow가 나거나 매우 큰 값이 작은 값처럼 보일 수 있습니다. 두 구간 중 하나라도 도달 불가능이면 갱신을 건너뛰어야 합니다.
음수 간선은 가능하지만 음수 사이클이 있으면 최단 거리 자체가 안정되지 않습니다. 계산 후 dist[i, i] < 0인 정점이 있는지 확인하세요.
참고 링크
1 sources