존슨 알고리즘

1. 개요[편집]

존슨 알고리즘 Johnson's algorithm
발표	Donald B. Johnson (1977)
푸는 문제	모든 쌍 최단경로 (APSP)
음의 가중치	허용 — 음수 사이클이면 검출 후 종료
핵심 장치	퍼텐셜 h에 의한 재가중
구성	벨만-포드 1회 + 다익스트라 V회
시간	이진힙 $O(VE\log V)$ · 피보나치힙 $O(VE + V^2\log V)$
유리한 곳	희소 그래프 — 조밀하면 플로이드-워셜

존슨 알고리즘은 음수 간선이 섞인 그래프에서 모든 정점 쌍 사이의 최단경로를, 간선 가중치를 한 번 «재가중»해 전부 비음수로 만든 뒤 각 정점에서 다익스트라 알고리즘을 돌려 구하는 알고리즘이다. 1977년 도널드 존슨이 희소 네트워크용 최단경로 논문에서 제시했다.¹

동기는 딱 하나다. 음수 간선이 있으면 다익스트라의 그리디 확정이 무너지고(다익스트라 알고리즘 문서의 반례 참고), 그렇다고 $V$ 번의 벨만-포드 알고리즘을 돌리면 $O(V^2E)$ 로 플로이드-워셜 알고리즘의 $O(V^3)$ 보다도 나쁘다. 존슨의 답은 느린 알고리즘을 딱 한 번만 쓰고, 그 한 번으로 빠른 알고리즘의 전제조건을 만들어 주는 것이다. 벨만-포드를 한 번 돌려 얻은 퍼텐셜로 음수를 지우고, 그 뒤의 $V$ 번 반복은 전부 다익스트라에게 넘긴다.

여기서 진짜 주인공은 알고리즘 껍데기가 아니라 퍼텐셜에 의한 재가중이라는 도구다. 같은 도구가 A* 알고리즘의 휴리스틱이자 네트워크 흐름 최소비용 유동의 감소비용이며, 선형계획 쌍대성의 쌍대 변수다. 이 문서의 절반은 그 도구에 대한 것이다.

2. 재가중이 최단경로 집합을 바꾸지 않는 이유[편집]

정점마다 실수 $h(v)$ 를 하나씩 붙이고 간선 가중치를 이렇게 바꾼다.

$$w'(u,v) \;=\; w(u,v) + h(u) - h(v)$$

이제 경로 $p = v_0 \to v_1 \to \cdots \to v_k$ 전체의 가중치를 재가중된 값으로 더해 보자.

$$w'(p) \;=\; \sum_{i=0}^{k-1}\Big[w(v_i,v_{i+1}) + h(v_i) - h(v_{i+1})\Big] \;=\; w(p) + \underbrace{h(v_0) - h(v_k)}_{\text{양 끝만 남는다}}$$

중간 정점의 $h$ 가 $+h(v_i)$ 와 $-h(v_i)$ 로 짝을 지어 전부 지워지는 망원합(telescoping sum)이다. 결론은 강력하다 — 같은 출발점 $s$ 와 같은 도착점 $t$ 를 잇는 모든 경로가 정확히 같은 상수 $h(s)-h(t)$ 만큼 이동한다. 경로들 사이의 대소 관계는 그대로이므로 최단경로 집합 자체가 불변이고, 거리는 나중에

$$\delta(s,t) \;=\; \delta'(s,t) - h(s) + h(t)$$

로 되돌리면 된다. 사이클($v_0 = v_k$)에서는 보정항이 0이라 사이클 가중치는 아예 변하지 않는다. 재가중으로 음수 사이클을 몰래 지워 버릴 수 없다는 뜻이고, 이게 알고리즘의 정합성에 결정적이다.

여기까지는 $h$ 가 무엇이든 성립한다. 남은 문제는 “모든 간선에서 $w' \ge 0$ 이 되게 하는 $h$ 를 어떻게 찾느냐”다.

3. 퍼텐셜은 최단거리 자신이다[편집]

$w'(u,v) \ge 0$ 을 풀어 쓰면 이렇다.

$$h(v) \;\le\; h(u) + w(u,v) \qquad \forall (u,v)\in E$$

이건 최단거리 함수가 만족하는 삼각부등식 그 자체다. 즉 어떤 점 $q$ 로부터의 최단거리 $h(v) = \delta(q,v)$ 를 쓰면 조건이 공짜로 만족된다. 최단거리가 삼각부등식을 어기면 그건 최단거리가 아니었을 테니까.

그런데 $q$ 를 그래프 안의 아무 정점으로 잡으면 거기서 도달 못 하는 정점의 $h$ 가 $+\infty$ 가 되어 재가중이 정의되지 않는다. 존슨의 처방이 가상 정점 $q$ 다.

• 새 정점 $q$ 를 만들고 $q \to v$ 간선을 모든 $v$ 에 대해 가중치 0으로 건다.
• $q$ 로 들어오는 간선은 없으므로 $q$ 는 어떤 최단경로에도 중간에 낄 수 없다. 즉 원래 그래프의 최단거리를 하나도 바꾸지 않는다.
• 모든 정점이 $q$ 에서 도달 가능하고, $h(v) \le w(q,v) = 0$ 이므로 퍼텐셜은 항상 0 이하다.

구현에서는 정점을 실제로 추가할 필요도 없다. 거리 배열을 전부 0으로 초기화하고 벨만-포드를 돌리면 결과가 똑같다 — 가상 정점에서 첫 라운드를 이미 마친 상태로 시작하는 셈이기 때문이다. 널리 쓰이는 한 줄짜리 트릭이다.²

음수 사이클이 있으면 이 단계에서 벨만-포드가 잡아낸다. 앞서 봤듯 재가중은 사이클 가중치를 건드리지 못하므로 “음수 사이클이 있는데 재가중해서 비음수로 만들었다”는 상황은 원리적으로 불가능하고, 따라서 벨만-포드가 통과했다는 사실 자체가 이후 다익스트라의 전제를 보증한다.

4. 절차와 복잡도[편집]

1. 가상 정점 $q$ 를 붙이고 벨만-포드로 $h(v) = \delta(q,v)$ 를 구한다. 음수 사이클이면 여기서 종료. — $O(VE)$
2. 모든 간선을 $w'(u,v) = w(u,v) + h(u) - h(v) \ge 0$ 으로 재가중한다. — $O(E)$
3. 각 정점 $s$ 를 출발점으로 다익스트라를 돌려 $\delta'(s,\cdot)$ 를 얻는다. — $V \times$ (다익스트라)
4. $\delta(s,t) = \delta'(s,t) - h(s) + h(t)$ 로 되돌린다. — $O(V^2)$

지배하는 것은 3단계다. 우선순위 큐를 무엇으로 쓰느냐가 그대로 총복잡도가 된다.

큐 구현	다익스트라 1회	존슨 전체
이진 힙	$O(E\log V)$	$O(VE\log V)$
피보나치 힙	$O(E + V\log V)$	$O(VE + V^2\log V)$
배열 선형탐색	$O(V^2)$	$O(V^3)$

$E = O(V)$ 인 희소 그래프에서 피보나치 힙 판은 $O(V^2\log V)$ 로, 플로이드-워셜 알고리즘의 $\Theta(V^3)$ 을 로그 인자 하나 빼고 $V$ 배 가까이 앞선다. 반대로 $E \sim V^2$ 인 조밀 그래프에서는 $O(V^3\log V)$ 가 되어 오히려 진다. 갈림길은 $E$ 대 $V^2/\log V$ 정도이고, 여기에 상수 항이 얹힌다 — 플로이드-워셜의 삼중 루프는 자료구조가 없고 메모리 접근이 연속적이라 상수가 극도로 작은 반면, 존슨은 힙 조작과 포인터 추적으로 캐시를 계속 때린다. 그래서 실측 손익분기점은 이론값보다 훨씬 희소한 쪽으로 밀려 있다.

5. 삼각부등식이라는 같은 얼굴[편집]

퍼텐셜 재가중은 존슨의 전유물이 아니다. 같은 물건이 이름만 바꿔 여러 번 등장한다.

• A* 알고리즘의 휴리스틱. $h$ 가 일관적(consistent)이라는 조건 $h(u) \le w(u,v) + h(v)$ 는 위의 부등식과 글자만 다르고, A*는 정확히 재가중된 그래프 위의 다익스트라다. 다만 부호 관습이 반대인데, 존슨의 $h$ 는 “시작점에서 여기까지”이고 A*의 $h$ 는 “여기서 목표까지”이기 때문이다.³
• 네트워크 흐름의 연속 최단경로법(SSP). 최소비용 유동에서 잔여 그래프에는 역방향 간선의 비용이 $-c(u,v)$ 로 들어와 반드시 음수 간선이 생긴다. 그래서 매 증가 단계마다 벨만-포드를 돌리면 $O(V E)$ 씩 깨지는데, 처음 한 번만 벨만-포드로 퍼텐셜을 잡고 이후에는 직전 다익스트라의 거리 자체를 새 퍼텐셜로 갱신($h \leftarrow h + \delta'$)하면 계속 비음수가 유지된다. 이 감소비용(reduced cost) $c^\pi(u,v) = c(u,v) + \pi(u) - \pi(v)$ 는 선형계획 쌍대성의 쌍대 변수 그 자체이고, 상보 여유 조건이 곧 “감소비용이 음수인 간선에는 흐름이 포화돼 있다”는 최적성 판정이 된다. 헝가리안 알고리즘의 라벨도 같은 물건이다.
• 차분 제약 시스템. $x_v - x_u \le w(u,v)$ 꼴 부등식 뭉치의 해가 곧 퍼텐셜이다. 존슨의 벨만-포드 단계는 사실 이 부등식계를 푸는 것이고, “해가 존재할 필요충분조건 = 음수 사이클이 없을 것”이 그대로 대응한다.

즉 존슨 알고리즘을 이해한다는 건 APSP 하나를 배우는 게 아니라 최소 비용 흐름과 최적화 쌍대성으로 통하는 문을 여는 것에 가깝다.

6. 구현에서 밟는 지뢰[편집]

• 도달 불가능 정점. $\delta'(s,t) = \infty$ 인 자리에 $-h(s)+h(t)$ 를 더하면 쓰레기값이 나온다. $\infty$ 판정을 먼저 하고 보정을 건너뛰어야 한다. INF를 큰 정수로 흉내 낸 코드에서 오버플로가 나는 전형적 자리이기도 하다.
• 되돌리기를 잊는 것. 3단계 결과 $\delta'$ 를 그대로 출력하는 실수가 흔하다. 재가중된 거리는 경로는 맞지만 값은 틀리다. 경로만 필요하다면(예: 선행자 배열) 되돌릴 필요가 없다는 점도 같이 기억해 두면 좋다.
• 다중 간선·자기 루프. 재가중은 간선 단위 연산이라 다중 간선이 있어도 문제없지만, 자기 루프 $w'(v,v) = w(v,v)$ 는 $h$ 가 상쇄돼 값이 그대로다. 음수 자기 루프는 길이 1짜리 음수 사이클이므로 벨만-포드가 잡아 준다.
• 병렬화. 3단계의 $V$ 번의 다익스트라는 서로 완전히 독립이라, 정점을 프로세스에 나눠 주기만 하면 통신 없이 선형 확장된다. 반면 플로이드-워셜은 $k$ 루프가 순차 의존이라 층마다 동기화가 필요하다. 존슨이 대형 클러스터에서 의외로 잘 버티는 이유다.
• 부동소수점. 가중치가 실수면 재가중 뺄셈에서 자릿수 소실이 일어나 $w'$ 가 $-10^{-15}$ 같은 값이 될 수 있고, 그 순간 다익스트라의 전제가 깨진다. 실무에서는 음수로 나온 $w'$ 를 0으로 클램프하는 처리를 넣는다. 정수 가중치면 이 문제가 없다.

7. 여담[편집]

• 존슨의 1977년 논문은 다익스트라에 $d$-진 힙을 붙여 $O(E\log_{E/V}V)$ 를 얻은 것으로도 유명한데, 정작 교과서에 이름이 남은 건 재가중 쪽이다. 같은 논문에서 나온 두 결과 중 덜 화려한 쪽이 이름을 가져간 사례.
• “존슨 알고리즘”이라는 이름은 최소 세 개 있다. 여기 이 APSP 알고리즘, 순열 생성의 존슨-트로터, 그리고 그래프의 모든 기본 사이클을 열거하는 존슨 알고리즘(1975, 같은 사람이다). 검색할 때 주의.
• 음수 가중치 단일 출발점 최단경로가 2022년에 거의 선형 시간으로 내려왔으므로(벨만-포드 알고리즘 참고), 원리적으로는 존슨의 1단계를 그것으로 갈아 끼울 수 있다. 다만 존슨의 병목은 애초에 $V$ 번의 다익스트라 쪽이라 총복잡도는 거의 안 변한다. 1단계를 아무리 빨리 만들어도 3단계가 안 줄면 소용없다 — 최적화의 아주 정직한 교훈.

8. 관련 문서[편집]

• 벨만-포드 알고리즘 · 다익스트라 알고리즘 · 플로이드-워셜 알고리즘
• A* 알고리즘 · 경로 계획 · 우선순위 큐
• 네트워크 흐름 · 최소 비용 흐름 · 헝가리안 알고리즘
• 쌍대성 · 선형계획법 · 조합 최적화
• 동적 계획법 · 최소 신장 트리 · 희소행렬

9. Footnotes[편집]

1. Johnson, D. B. (1977). “Efficient algorithms for shortest paths in sparse networks”. JACM 24(1), 1–13. 제목에 sparse가 박혀 있다는 게 이 알고리즘의 존재 이유를 그대로 말해 준다. 조밀하면 애초에 쓸 이유가 없다. ↩

2. 이걸 보고 “가상 정점은 설명용 허구였구나” 하고 넘기면 곤란하다. 정당성 증명은 여전히 $q$ 가 있어야 깔끔하게 굴러간다. 구현에서 사라지는 것이지 논리에서 사라지는 게 아니다. 수학과 코드가 다른 것을 보는 전형적인 자리. ↩

3. 그래서 두 문헌을 나란히 놓고 읽으면 부호가 안 맞아 한참 헤맨다. 어느 쪽이든 확인법은 같다 — 비음수가 되는 방향이 맞는 방향이다. 부호를 외우지 말고 삼각부등식을 한 번 쓰는 게 빠르다. ↩