Johnson's Algorithm: sparse APSP

Johnson's Algorithm, 존슨 알고리즘

정의

Johnson’s algorithm 은 sparse graph 의 all-pairs shortest paths 를 O(V·E log V + V²) 에 계산. Bellman-Ford + Dijkstra 조합.

알고리즘

1. 임시 정점 s 추가, 모든 정점에 가중치 0 간선 연결
2. Bellman-Ford 로 h[v] = dist(s, v) 계산
3. 각 간선 (u, v) 재가중: w’(u, v) = w(u, v) + h[u] - h[v] ≥ 0
4. 재가중 그래프에서 각 정점을 소스로 Dijkstra 실행
5. 원래 거리 복원: d(u, v) = d’(u, v) - h[u] + h[v]

핵심: Bellman-Ford 로 potential 을 만든 뒤 non-negative 재가중, Dijkstra 사용 가능하게 함.

복잡도 비교

방법	복잡도	조건
Floyd-Warshall	O(V³)	Any
Johnson	O(VE log V)	negative allowed
Dijkstra × V	O(V² log V + VE)	non-negative

Sparse (E = O(V)) 일 때 Johnson 이 Floyd-Warshall 보다 빠름.

참고

• Floyd-Warshall
• Dijkstra
• Bellman-Ford