모든 쌍 최단경로(플로이드–워셜) 계산기
간선 목록을 넣으면 모든 정점 쌍의 최단거리를 행렬로 내고 경로도 되짚어 줍니다. 음수 간선을 그대로 다루며, 대각선이 음수가 되는 것으로 음수 사이클을 잡아냅니다. k를 안쪽에 두면 답이 어떻게 달라지는지도 함께 보여 줍니다.
한 줄에 «출발 도착 가중치» 하나씩. 가중치는 음수도 됩니다. 정점 30개까지.
정점 4개 · 쌍 16개
10쌍에 길이 있습니다
못 가는 쌍이 6개 있습니다. 방향이 있는 그래프라 되돌아가는 길은 따로 적어야 합니다.
a → d
거리 4
a → b → c → d
거리 행렬
| 출발 → 도착 | a | b | c | d |
|---|---|---|---|---|
| a | 0 | 1 | 3 | 4 |
| b | ∞ | 0 | 2 | 3 |
| c | ∞ | ∞ | 0 | 1 |
| d | ∞ | ∞ | ∞ | 0 |
대각선을 보세요. 자기 자신으로 돌아오는 비용이라 보통은 0인데, 여기가 음수면 그 정점이 음수 사이클 위에 있다는 뜻입니다. 돌수록 짧아지니 최단거리라는 개념 자체가 없어집니다. 음수 사이클 검출이 「다 돌린 뒤 대각선을 한 번 보는 것」으로 끝나는 이유입니다.
k를 안쪽에 두면
이 그래프에서는 반복문 순서를 바꿔도 답이 같습니다. 늘 같은 것은 아닙니다 — 위 「루프 순서 함정」 예제를 넣어 보면 답이 갈라집니다.
사용 방법
- 1간선을 한 줄에 하나씩 «출발 도착 가중치» 형식으로 적습니다.
- 2거리 행렬에서 모든 쌍의 최단거리를 확인합니다.
- 3출발과 도착을 골라 실제 경로를 봅니다.
- 4대각선에 음수가 있는지 보아 음수 사이클을 확인합니다.
- 5「k를 안쪽에 두면」에서 반복문 순서가 왜 중요한지 확인합니다.
자주 묻는 질문
삼중 반복문 하나가 전부입니다. 거쳐 갈 정점 k를 하나씩 늘려 가며 모든 (i, j) 쌍에 대해 d[i][j]와 d[i][k] + d[k][j] 중 짧은 쪽을 남깁니다. 정점 수의 세제곱만큼 걸리지만 코드가 세 줄이라 구현이 쉽습니다.
k가 「거쳐 가도 되는 정점의 범위」를 뜻하기 때문입니다. k번째 바퀴가 끝난 시점의 d[i][j]는 「0번부터 k번 정점까지만 거쳐 가는 최단거리」인데, 이 불변식이 성립하려면 k 바퀴 하나가 통째로 끝나야 합니다. k를 안쪽에 두면 d[i][k]나 d[k][j]가 아직 갱신되지 않은 값일 수 있어 더 짧은 길을 놓칩니다.
값이 엉뚱하게 나오는 것이 아니라 「덜 줄어든 채」 남습니다. 틀린 결과는 언제나 올바른 거리보다 크거나 같아서, 답이 크게 어긋나지 않아 눈에 잘 띄지 않습니다. 이 실수가 오래 사는 이유이고, 이 도구는 두 순서를 모두 계산해 갈린 쌍을 짚어 줍니다.
다익스트라는 출발점 하나에서의 최단거리를 구하고 음수 간선을 다루지 못합니다. 「가장 가까운 것을 확정하면 다시 줄지 않는다」는 가정에 기대는데 음수 간선이 있으면 그 가정이 무너지기 때문입니다. 플로이드–워셜은 그런 가정을 쓰지 않아 음수 간선을 그대로 다루고 모든 쌍을 한 번에 구합니다. 대신 출발점 하나만 필요하다면 다익스트라가 훨씬 빠릅니다.
다 돌린 뒤 대각선 d[i][i]를 보면 됩니다. 자기 자신으로 돌아오는 비용이 음수라는 것은 그 정점이 음수 사이클 위에 있다는 뜻입니다. 그런 사이클을 지나는 경로는 돌수록 짧아지므로 최단거리라는 개념 자체가 없어 −∞로 표시합니다.
두 줄로 적어야 합니다. 이 도구는 방향이 있는 그래프로 읽으므로 «a b 3»은 a에서 b로만 갈 수 있다는 뜻입니다. 양쪽으로 오갈 수 있다면 «b a 3»도 함께 적으세요.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- 정답지는 벨먼–포드입니다. 출발점 하나씩 벨먼–포드를 돌려 모든 쌍의 거리를 따로 구하고 결과를 대조합니다. 두 알고리즘은 원리가 다르지만(간선을 V−1 바퀴 훑는 것과 거쳐 갈 정점을 하나씩 늘리는 것) 음수 간선을 다루고 음수 사이클을 잡는 성질이 같아 서로를 검산하기에 알맞습니다.
- 되짚은 경로가 실제로 그 거리와 맞는지도 검사합니다. 경로에 실린 간선의 가중치를 모두 더한 값이 행렬의 거리와 같아야 하며, 여섯 가지 그래프의 모든 쌍에서 이를 확인했습니다.
- k를 안쪽에 둔 판도 함께 계산해 두 결과가 갈리는 쌍을 찾습니다. 틀린 쪽이 언제나 올바른 거리보다 크거나 같다는 것(덜 줄어든 채 남는다는 것)도 테스트로 고정했습니다.
- 음수 사이클 검출은 대각선이 음수인지만 봅니다. 벨먼–포드가 「V−1 바퀴 뒤에도 계속 줄어드는 정점」으로 찾아내는 집합과 같은 정점들이 −∞로 표시되는지 대조했습니다.
- 음수 사이클과 상관없는 정점은 −∞가 되지 않아야 합니다. 사이클에 가지도 오지도 못하는 부분 그래프의 거리가 그대로 남는지 따로 검사합니다.
- 간선 입력은 dijkstra-path와 같은 파서를 그대로 씁니다. 두 도구를 오가며 같은 그래프를 넣어 볼 수 있습니다.
- 정점은 30개까지 다루고 거리 행렬은 12개까지 통째로 그립니다. 같은 쌍에 간선이 여럿이면 짧은 쪽만 씁니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.