Quick Comparison
| 조건 | 내용 |
|---|---|
| 대상 | 음수 간선이 있을 수 있는 가중치 그래프 |
| 결과 | 시작점에서 각 정점까지의 최단 거리 |
| 시간 | O(VE) |
| 음수 사이클 | V번째 완화에서 거리가 줄어들면 의심 |
int[] previous = new int[n];
Array.Fill(previous, -1);
for (int i = 0; i < n - 1; i++)
{
bool changed = false;
foreach ((int from, int to, long cost) in edges)
{
if (dist[from] == INF) continue;
long through = checked(dist[from] + cost);
if (dist[to] <= through) continue;
dist[to] = through;
previous[to] = from;
changed = true;
}
if (!changed) break;
}음수 간선이 하나라도 있으면 다익스트라 대신 Bellman-Ford를 고릅니다. 시작점에서 닿지 않는 음수 사이클은 이 실행의 최단 거리에는 영향을 주지 않습니다.
구조
Bellman-Ford는 모든 간선을 반복해서 완화합니다. 최단 경로가 사이클을 포함하지 않는다면 최대 간선 수는 V - 1개이므로, V - 1번 반복하면 도달 가능한 최단 거리가 모두 반영됩니다.
완화:
dist[to] > dist[from] + cost 이면
dist[to]를 더 짧은 값으로 갱신다익스트라처럼 가장 가까운 후보를 확정하지 않기 때문에 음수 간선도 처리할 수 있습니다. 대신 매 반복마다 모든 간선을 보므로 정점과 간선이 많으면 비용이 큽니다.
음수 사이클 감지
V - 1번 이후에도 거리가 줄어든다면 단순 경로보다 더 짧아지는 반복 구조가 있다는 뜻입니다. 시작점에서 도달 가능한 음수 사이클이 있으면 최단 거리는 정의되지 않습니다.
bool hasNegativeCycle = false;
foreach ((int from, int to, long cost) in edges)
{
if (dist[from] == INF) continue;
long through = checked(dist[from] + cost);
if (dist[to] > through)
{
hasNegativeCycle = true;
break;
}
}경로와 사이클 복원
완화할 때 previous[to] = from을 함께 저장하면 음수 사이클이 없을 때 목표 정점에서 시작점까지 부모를 거슬러 경로를 복원할 수 있습니다. 시작점의 previous는 -1로 둡니다.
static List<int> RestorePath(int source, int target, int[] previous, long[] dist, long inf)
{
if (dist[target] == inf) return new List<int>();
var path = new List<int>();
for (int current = target; current != -1; current = previous[current])
{
path.Add(current);
if (current != source) continue;
path.Reverse();
return path;
}
return new List<int>(); // predecessor가 시작점까지 이어지지 않는 잘못된 입력
}V번째 완화에서 갱신된 정점을 lastUpdated로 남겼다면, previous[lastUpdated]를 V번 따라가 음수 사이클 안의 정점으로 들어갈 수 있습니다. 그 뒤 시작 정점으로 돌아올 때까지 predecessor를 모으면 사이클 자체를 복원할 수 있습니다. 이 작업은 정수 가중치와 overflow 없는 거리 연산을 전제로 합니다.
선택 기준
| 문제 조건 | 알고리즘 |
|---|---|
| 간선 비용이 모두 1 | BFS |
| 음수 간선이 없음 | 다익스트라 |
| 음수 간선이 있음 | Bellman-Ford |
| 모든 쌍 최단 거리, 정점 수 작음 | Floyd-Warshall |
| 차익 거래, 무한 감소 경로 | 음수 사이클 감지 |
Bellman-Ford는 음수 간선 자체보다 음수 사이클 여부가 중요한 문제에서도 자주 쓰입니다. 거리값이 필요한지, 사이클 존재만 필요한지에 따라 마지막 검사를 더 강조합니다.
주의할 점
도달할 수 없는 정점의 INF 값을 그대로 더하면 overflow나 잘못된 갱신이 생길 수 있습니다. 간선을 완화하기 전에 dist[from] == INF를 반드시 확인하고, 문제의 최대 경로 절대값이 long 범위에 들어오는지 확인하세요.
음수 사이클은 시작점에서 도달 가능한 경우에만 현재 dist 배열로 감지됩니다. 그래프 전체의 음수 사이클을 찾는 문제라면 모든 정점을 시작 후보로 보거나, 가상의 시작점을 연결하는 방식이 필요합니다.
참고 링크
1 sources