Quick Comparison
정점 수가 작고, 출발점과 도착점 조합을 여러 번 물을 때 선택합니다. 한 시작점만 필요하면 다익스트라나 Bellman-Ford가 보통 더 적합합니다.
| 조건 | 내용 |
|---|---|
| 대상 | 모든 정점 쌍 최단 거리 |
| 시간 | O(V³) |
| 공간 | O(V²) |
| 음수 간선 | 가능 |
| 음수 사이클 | dist[k, k] < 0이면 k를 지나는 경로는 유한한 최단 거리가 없음 |
구조
Floyd-Warshall은 k번 정점을 경유지로 사용할 수 있을 때 최단 거리가 줄어드는지 확인합니다. 핵심은 반복 순서입니다. k가 가장 바깥에 있어야 “0..k까지의 정점만 중간 경유지로 허용한다”는 DP 의미가 유지됩니다.
dist[i, j] = i에서 j로 바로 가는 거리
dist[i, j] = min(dist[i, j], dist[i, k] + dist[k, j])초기화는 결과를 크게 좌우합니다. 자기 자신은 0, 간선이 없으면 INF, 여러 간선이 있으면 더 작은 비용을 저장합니다. 아래 구현은 next[i, j]에 경로에서 i 다음에 갈 정점을 함께 보관하므로 거리와 경로를 모두 구합니다. 입력의 절대 거리 합이 INF보다 충분히 작다는 전제입니다.
static (long[,] Distance, int[,] Next) AllPairs(
int vertexCount,
IEnumerable<(int From, int To, long Cost)> edges)
{
const long INF = long.MaxValue / 4;
var distance = new long[vertexCount, vertexCount];
var next = new int[vertexCount, vertexCount];
for (int i = 0; i < vertexCount; i++)
{
for (int j = 0; j < vertexCount; j++)
{
distance[i, j] = i == j ? 0 : INF;
next[i, j] = -1;
}
}
foreach ((int from, int to, long cost) in edges)
{
if (cost <= -INF || cost >= INF) throw new ArgumentOutOfRangeException(nameof(edges));
if (cost >= distance[from, to]) continue;
distance[from, to] = cost;
next[from, to] = to;
}
for (int k = 0; k < vertexCount; k++)
{
for (int i = 0; i < vertexCount; i++)
{
if (distance[i, k] == INF) continue;
for (int j = 0; j < vertexCount; j++)
{
if (distance[k, j] == INF) continue;
long throughK = distance[i, k] + distance[k, j];
if (throughK >= distance[i, j]) continue;
distance[i, j] = throughK;
next[i, j] = next[i, k];
}
}
}
return (distance, next);
}k가 가장 바깥 반복문이어야 합니다. i, j, k 순서로 바꾸면 이번 단계에서 허용하지 않은 경유지를 다시 써서 DP의 의미가 깨집니다.
경로와 음수 사이클
next가 -1이면 두 정점 사이에 경로가 없습니다. start에서 goal까지 실제 정점 순서가 필요할 때만 아래처럼 복원합니다.
static List<int> RestorePath(int[,] next, int start, int goal)
{
if (next[start, goal] == -1) return [];
var path = new List<int> { start };
while (start != goal)
{
start = next[start, goal];
path.Add(start);
}
return path;
}계산 뒤 dist[k, k] < 0이면 k를 한 번 더 지날수록 비용을 계속 줄일 수 있는 음수 사이클이 있습니다. i에서 k에 도달할 수 있고 k에서 j에 도달할 수 있으면 i → j의 값도 유한한 최단 거리로 해석하면 안 됩니다. 단순히 대각선만 검사하고 dist[i, j]를 답으로 내보내는 실수를 피하세요.
선택 기준
| 문제 조건 | 판단 |
|---|---|
| 모든 출발점과 도착점의 최단 거리 필요 | Floyd-Warshall |
| 정점 수가 작고 질의가 많음 | Floyd-Warshall |
| 정점 수가 크고 시작점 하나만 필요 | Dijkstra 또는 Bellman-Ford |
| 간선 비용이 모두 1 | 각 시작점 BFS 검토 |
| 도달 가능성만 필요 | transitive closure로 변형 가능 |
정점 수가 500이면 약 1억 2500만 번의 갱신이 필요합니다. 언어와 시간 제한에 따라 가능할 수 있지만, 정점 수가 1000을 넘으면 대부분 부담이 커집니다. V² 거리 행렬의 메모리도 별도로 계산해야 합니다.
주의할 점
INF + cost를 계산하면 overflow가 나거나 매우 큰 값이 작은 값처럼 보일 수 있습니다. 두 구간 중 하나라도 도달 불가능이면 갱신을 건너뛰어야 합니다. long.MaxValue / 4처럼 덧셈 여유가 있는 상한을 쓰고, 문제의 최대 경로 비용이 그 상한보다 작은지 확인하세요.
음수 간선은 가능하지만 음수 사이클이 있으면 최단 거리 자체가 안정되지 않습니다. 계산 후 dist[i, i] < 0인 정점이 있는지 확인하세요.
참고 링크
1 sources