yg log --graph --oneline --all

Home Stack Notes AboutRSS

13. 최단 경로는 음수 간선에서 갈라진다

작성 · 6분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

출발점에서 누적 비용을 최소화하는 문제

입력은 방향 또는 무방향 가중 그래프와 출발 정점이다. 원하는 답은 출발점에서 각 정점까지 갈 수 있는 경로 중 가중치 합이 가장 작은 값이다.

간선: 0→1(4), 0→2(1), 2→1(2)
출발: 0
0에서 1까지 직접 비용: 4
0→2→1 비용: 1+2=3
최단 거리 dist[1]: 3

경로 비용은 경로에 포함된 간선 가중치의 합이다. 최단 거리는 가능한 경로 비용의 최솟값이고, 실제로 그 값을 만드는 정점 나열을 최단 경로라고 한다. 도달할 수 없는 정점에는 유한한 경로 비용이 없으므로 코드에서는 INF 같은 별도 상태를 둔다.

최단 경로 알고리즘의 공통 연산은 완화(relaxation)다. 현재 dist[u]를 알고 있을 때 간선 u→v를 붙인 새 후보 dist[u]+w(u,v)가 기존 dist[v]보다 작으면 값을 바꾼다.

식의 항 뜻
dist[u] 출발점에서 u까지 현재까지 알려진 최선의 비용
w(u,v) u에서 v로 가는 마지막 간선 하나의 비용
dist[u]+w(u,v) u를 거쳐 v에 도착하는 새 경로 후보
dist[v] 지금까지 알고 있던 v의 최선 비용

Dijkstra와 Bellman-Ford는 같은 완화를 사용한다. 차이는 어느 정점을 확정할 수 있는지, 모든 간선을 몇 번 다시 확인하는지다.

최단 경로가 없다는 말의 범위

최단 경로 노트에는 이렇게 적혀 있다.

가중 방향그래프에 음의 무게를 가진 싸이클이 존재한다면, 최단경로는 존재하지 않는다

노트는 정의와 속성을 정리한 짧은 목록이다. 이 문장의 예외를 당시 직접 실험하거나 해결한 기록은 없다. 이번에는 같은 문장을 출발점과 도착점을 지정한 작은 그래프로 다시 읽었다.

0에서 1로 가는 비용 2의 간선이 있고, 이들과 떨어진 2와 3 사이에 음수 순환이 있다고 하자. 0에서 그 순환으로 갈 수 없다면 0→1의 최단 거리는 여전히 2다. 그래프 어딘가에 음수 순환이 있다는 이유만으로 모든 답이 사라지지는 않는다.

출발점에서 그 순환에 도달할 수 있고, 순환에서 도착점으로 나갈 수 있을 때 비용을 계속 낮출 수 있다. 이 글에서 경로 비용을 최소화할 때는 정점과 간선을 다시 지나는 이동을 허용한다. 순환을 반복할수록 값이 작아져 유한한 최솟값이 없다는 뜻이다. 단순 경로만 허용하는 별도 문제와는 구분한다. Algorithms, 4th Edition의 음수 순환과 최단 경로 존재 조건

최소신장트리의 key에 거리를 더하면 다른 문제가 된다

최소신장트리 글에서는 현재 나무와 v를 잇는 간선 하나의 무게를 key[v]에 넣었다. 최단 경로에서는 dist[v]가 출발점부터 v까지의 전체 비용이다.

if (dist[u] != INF && dist[u] + weight < dist[v]) {
    dist[v] = dist[u] + weight;
}

이 갱신을 완화라고 한다. 이미 아는 u까지의 길에 u→v 간선을 붙여 보았더니 더 싸면 답 후보를 바꾸는 것이다. 핵심은 weight 하나와 비교하는 것이 아니라 dist[u] + weight와 비교한다는 데 있다.

INF는 아직 도달하지 못했다는 표시다. 그 값에 음수를 더해 우연히 더 작은 숫자를 만들면 존재하지 않는 경로를 발견한 것처럼 처리할 수 있다. 따라서 덧셈 전에 도달 여부부터 확인한다. 이번 코드는 정점 최대 16개, 간선 무게 절댓값 최대 1,000인 검증용 입력에 한정하고, long long과 충분히 큰 INF를 사용했다. 입력 범위가 바뀌면 덧셈 범위도 다시 확인해야 한다.

Dijkstra가 확정해도 되는 순간

Dijkstra는 아직 확정하지 않은 정점 중 현재 거리가 최소인 u를 고른다. 모든 간선 무게가 0 이상이면, 다른 미확정 정점을 거쳐 나중에 u로 오는 길이 지금의 값보다 작아질 수 없다. 중간에 거리를 줄여 주는 음수 간선이 없기 때문이다.

하지만 다음 그래프에서는 그 근거가 사라진다.

0 -> 1 :  2
0 -> 2 :  5
2 -> 1 : -4

0의 간선을 먼저 반영하면 dist[1]=2, dist[2]=5다. “가장 작은 값 2를 확정하고 다시 열지 않는다”는 구현은 1을 먼저 닫는다. 그러나 나중에 2를 거쳐 오면 5-4=1로 더 싸다. 음수 순환 없이도 확정 규칙이 틀릴 수 있다.

그래서 이번 dijkstra는 입력에서 음수 간선을 발견하면 실행을 거절하도록 했다. 음수를 처리하려고 확정한 정점을 다시 열기 시작하면 여기서 설명하는 Dijkstra의 동작과 시간 보장을 그대로 적용할 수 없다. 배열로 최솟값을 고르는 이번 버전의 시간은 O(V²+E)이며, 힙을 쓰는 구현과 구분했다.

Bellman-Ford는 갱신할 기회를 반복한다

Bellman-Ford는 정점 하나를 영원히 확정하는 대신 간선 전체를 여러 번 완화한다. 출발점에서 도달 가능한 음수 순환의 영향을 받지 않는 최단 경로는 단순 경로로 고를 수 있고, 그 간선 수는 최대 V-1개다. 따라서 V-1번의 전체 순회면 필요한 갱신이 전파된다. 한 순회에서 갱신된 값을 바로 재사용하는 구현은 더 빨리 전파될 수 있지만 이 상한은 유지된다.

for (int pass = 1; pass < g->n; ++pass) {
    bool changed = false;
    for (int i = 0; i < m; ++i) {
        Edge e = edges[i];
        if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
            dist[e.v] = dist[e.u] + e.w;
            changed = true;
        }
    }
    if (!changed) break;
}

아까의 세 정점 예제에서는 다음 순서로 값이 바뀐다. 간선 배열의 검사 순서는 0→1, 0→2, 2→1이다.

시점 dist[0] dist[1] dist[2]
초기화 0 INF INF
0→1 반영 0 2 INF
0→2 반영 0 2 5
2→1 반영 0 1 5

다음 순회에서 바뀌는 값이 없으면 종료한다. 새 실행에서도 도달 불가능한 정점 하나를 추가해 0 1 5 unreachable을 얻었다. 일반적인 최악 시간은 간선 전체를 V번 정도 검사하는 O(VE)이고, 초기화와 그래프 읽기 비용까지 쓰면 O(V+E+VE)다.

음수 순환의 영향을 뒤쪽으로 전파한다

V-1번 이후에도 도달 가능한 간선을 완화할 수 있다면 음수 순환의 영향이 남아 있다. 그렇다고 함수의 모든 dist를 한꺼번에 무효 처리할 필요는 없다. 추가로 감소 가능한 간선의 도착점을 표시하고, 그 정점들에서 갈 수 있는 곳을 큐로 전파했다.

결과는 세 상태로 나뉜다.

상태 의미
dist[v] == INF 출발점에서 도달할 수 없음
bad[v] == true 도달 가능한 음수 순환을 거쳐 비용을 끝없이 낮출 수 있음
둘 다 아님 유한한 최단 거리

예를 들어 0→1 뒤에 음수 순환 2↔3을 연결해도, 그 순환에서 1로 돌아오는 길이 없다면 1의 유한한 답은 남는다. 무방향 그래프의 음수 간선은 왕복을 허용할 때 그 간선만 오가도 비용이 줄어드는 반면, 방향 그래프의 음수 간선 하나는 그 자체로 순환이 아니다.

새 검증에서는 세 정점의 여섯 방향 간선 자리에 없음, -2, 0, 3을 배정한 4,096개 그래프를 만들었다. 각 출발점에 대해 Bellman-Ford의 유한 거리와 음수 순환 영향 표시를 Floyd-Warshall 결과와 대조했다. 음수가 없는 경우에는 Dijkstra의 거리도 비교했고, 출발점과 떨어진 음수 순환도 따로 확인했다.

노트의 짧은 문장은 이제 “어디에 음수가 있는가”뿐 아니라 “그곳에 갈 수 있고 다시 어디로 나올 수 있는가”를 함께 묻는 문장으로 바뀐다. 최단 경로의 답을 하나의 숫자로만 두지 않고, 그 숫자가 존재하는 조건까지 반환하는 이유다.

기록과 실행 코드

관련 포스트