핵심 정리
| 조건 | 내용 |
|---|---|
| 대상 | 음수 간선이 있을 수 있는 가중치 그래프 |
| 결과 | 시작점에서 각 정점까지의 최단 거리 |
| 시간 | O(VE) |
| 음수 사이클 | V번째 완화에서 거리가 줄어들면 의심 |
csharp
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;
if (dist[to] <= dist[from] + cost) continue;
dist[to] = dist[from] + cost;
changed = true;
}
if (!changed) break;
}구조
Bellman-Ford는 모든 간선을 반복해서 완화합니다. 최단 경로가 사이클을 포함하지 않는다면 최대 간선 수는 V - 1개이므로, V - 1번 반복하면 도달 가능한 최단 거리가 모두 반영됩니다.
text
완화:
dist[to] > dist[from] + cost 이면
dist[to]를 더 짧은 값으로 갱신다익스트라처럼 가장 가까운 후보를 확정하지 않기 때문에 음수 간선도 처리할 수 있습니다. 대신 매 반복마다 모든 간선을 보므로 정점과 간선이 많으면 비용이 큽니다.
음수 사이클 감지
V - 1번 이후에도 거리가 줄어든다면 단순 경로보다 더 짧아지는 반복 구조가 있다는 뜻입니다. 시작점에서 도달 가능한 음수 사이클이 있으면 최단 거리는 정의되지 않습니다.
csharp
bool hasNegativeCycle = false;
foreach ((int from, int to, long cost) in edges)
{
if (dist[from] == INF) continue;
if (dist[to] > dist[from] + cost)
{
hasNegativeCycle = true;
break;
}
}선택 기준
| 문제 조건 | 알고리즘 |
|---|---|
| 간선 비용이 모두 1 | BFS |
| 음수 간선이 없음 | 다익스트라 |
| 음수 간선이 있음 | Bellman-Ford |
| 모든 쌍 최단 거리, 정점 수 작음 | Floyd-Warshall |
| 차익 거래, 무한 감소 경로 | 음수 사이클 감지 |
Bellman-Ford는 음수 간선 자체보다 음수 사이클 여부가 중요한 문제에서도 자주 쓰입니다. 거리값이 필요한지, 사이클 존재만 필요한지에 따라 마지막 검사를 더 강조합니다.
주의할 점
도달할 수 없는 정점의 INF 값을 그대로 더하면 overflow나 잘못된 갱신이 생길 수 있습니다. 간선을 완화하기 전에 dist[from] == INF를 반드시 확인하세요.
음수 사이클은 시작점에서 도달 가능한 경우에만 현재 dist 배열로 감지됩니다. 그래프 전체의 음수 사이클을 찾는 문제라면 모든 정점을 시작 후보로 보거나, 가상의 시작점을 연결하는 방식이 필요합니다.
참고 링크
1 sources