존슨 알고리즘(전체 쌍 최단경로) 계산기
간선 목록을 넣으면 벨만-포드로 퍼텐셜을 구해 음수를 없앤 뒤, 정점마다 다익스트라를 돌려 모든 쌍의 최단거리를 구합니다. 희소 그래프에서 음수 간선을 다루는 가장 빠른 방법이며, 퍼텐셜·재가중 과정을 단계별로 보여 줍니다.
한 줄에 «출발 도착 가중치» 하나씩. 방향이 있는 그래프이고 음수도 됩니다. 정점 60개까지.
정점 5개 · 간선 9개
음수 간선을 보정해 모든 쌍을 구했습니다
퍼텐셜로 재가중한 뒤 정점마다 다익스트라를 돌렸습니다. 다익스트라는 원래 음수 간선에서 못 씁니다.
1 → 3
거리 -3
1 → 5 → 4 → 3
1단계 — 퍼텐셜 h
가상 정점에서 모든 정점으로 0짜리 간선을 그어 벨만-포드를 한 번 돌린 거리입니다. 이 값으로 간선을 다시 그으면 음수가 사라집니다.
| 정점 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| h | 0 | -1 | -5 | 0 | -4 |
2단계 — 재가중된 간선
w'(u,v) = w(u,v) + h(u) − h(v). 이론대로 전부 0 이상이 됩니다.
| 간선 | 원래 가중치 | 재가중 |
|---|---|---|
| 1 → 2 | 3 | 4 |
| 1 → 3 | 8 | 13 |
| 1 → 5 | -4 | 0 |
| 2 → 4 | 1 | 0 |
| 2 → 5 | 7 | 10 |
| 3 → 2 | 4 | 0 |
| 4 → 1 | 2 | 2 |
| 4 → 3 | -5 | 0 |
| 5 → 4 | 6 | 2 |
3단계 — 최단거리 행렬
재가중된 그래프에서 정점마다 다익스트라를 돌린 뒤 상쇄분(h)을 다시 뺀 결과입니다.
| 출발 → 도착 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | -3 | 2 | -4 |
| 2 | 3 | 0 | -4 | 1 | -1 |
| 3 | 7 | 4 | 0 | 5 | 3 |
| 4 | 2 | -1 | -5 | 0 | -2 |
| 5 | 8 | 5 | 1 | 6 | 0 |
사용 방법
- 1간선을 한 줄에 «출발 도착 가중치» 형식으로 적습니다. 음수 가중치도 됩니다.
- 21단계 표에서 정점마다 구해진 퍼텐셜 h를 확인합니다.
- 32단계 표에서 재가중된 간선이 모두 0 이상이 되는 것을 확인합니다.
- 4출발과 도착을 골라 원래 가중치 기준 실제 최단경로를 봅니다.
- 5정점이 12개 이하면 전체 최단거리 행렬도 함께 봅니다.
자주 묻는 질문
희소 그래프(간선이 정점 수의 제곱보다 훨씬 적은 그래프)에서 음수 가중치를 허용하며 모든 정점 쌍의 최단거리를 빠르게 구하기 위한 것입니다. 벨만-포드를 딱 한 번 돌려 음수를 없애는 보정값(퍼텐셜)을 구한 뒤, 나머지는 빠른 다익스트라에 맡깁니다.
모든 정점에 가중치 0인 간선을 긋는 가상의 시작점을 하나 만들어, 거기서 벨만-포드를 한 번 돌린 거리가 h입니다. 가상 시작점이 모든 정점에 직접 닿으므로 h의 초깃값을 0으로 두고 벨만-포드를 돌리는 것과 같습니다.
벨만-포드가 수렴했다는 것은 모든 간선 (u, v)에서 h(v) ≤ h(u) + w(u, v)라는 뜻입니다(그렇지 않으면 아직 완화할 간선이 남은 것입니다). 이 부등식을 옮기면 w(u, v) + h(u) − h(v) ≥ 0이 바로 나옵니다.
어떤 경로든 재가중된 합은 원래 합에 h(출발) − h(도착)만 더해지고 중간 정점의 h는 전부 상쇄되기 때문입니다. 모든 경로에 똑같은 상수가 더해지므로 어느 경로가 가장 짧은지는 바뀌지 않습니다. 그래서 재가중된 그래프의 다익스트라 결과에서 그 상수만 다시 빼면 원래 최단거리가 됩니다.
플로이드–워셜은 O(V³)이 걸려 정점이 늘수록 급격히 느려지고, 정점마다 벨만-포드를 돌리면 O(V²·E)입니다. 존슨 알고리즘은 벨만-포드를 한 번만 돌리고 나머지는 O(V log V + E)인 다익스트라에 맡기므로 O(V²log V + VE)이며, 간선이 적은 그래프일수록 유리합니다.
퍼텐셜 자체가 정의되지 않아 계산할 수 없다고 알립니다. 가상 시작점이 모든 정점에 닿기 때문에 그래프 어디에 음수 순환이 있어도 이 한 번의 벨만-포드가 반드시 찾아냅니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기의 localStorage에만 남습니다.
알아두면 좋은 점
- 정답지는 CLRS(Introduction to Algorithms) 3판 25장의 존슨 알고리즘 예제 그래프와 책에 실린 최단거리 행렬입니다. 5개 정점, 음수 간선이 섞여 있지만 음수 순환은 없는 그래프이며, 이 도구의 결과가 책의 행렬과 정확히 일치하는지 확인했습니다.
- 재가중된 간선이 이론대로 모두 0 이상이 되는지도 별도로 검사합니다.
- 무작위 방향 비순환 그래프(DAG) 20개에서 이 도구와 dev/bellman-ford를 정점마다 따로 돌린 결과가 모든 쌍에서 일치하는지 대조했습니다. DAG는 사이클이 없어 가중치를 아무리 섞어도 음수 순환이 생기지 않으므로 대조에 알맞습니다.
- 되짚은 경로에 실린 간선의 가중치를 실제로 더해 거리표와 같은지도 검사합니다.
- 음수 순환이 있으면 그 순환에서 갈 수 있는 정점만 표시합니다. 순환과 무관한 정점은 영향을 받지 않습니다.
- 정점은 60개까지 다루고, 최단거리 행렬은 12개까지 통째로 그립니다. 같은 쌍에 간선이 여럿이면 다익스트라 단계에서 자연히 짧은 쪽이 남습니다.
- 간선 입력 형식은 dijkstra-path·bellman-ford·floyd-warshall과 같은 파서를 그대로 씁니다. 이 도구는 항상 방향이 있는 그래프로 읽습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 8일 · 결과는 참고용 추정치입니다.