벨만-포드 최단경로 계산기

«가장 가까운 정점부터 확정»하지 않고 모든 간선을 정점 수 − 1번 훑으며 거리를 줄이기만 합니다. 그래서 O(V·E)로 느리지만, 음수 가중치가 있어도 정확하고 음수 순환까지 잡아냅니다. 다익스트라는 빠른 대신 음수 간선에서 답이 틀립니다.

최단경로는 같은 정점을 두 번 지나지 않으므로 간선을 많아야 V − 1개 쓰기 때문입니다. 한 회차마다 «간선 하나만큼 더 뻗은» 최단경로가 반드시 확정되므로 V − 1회차면 모두 완성됩니다. 다만 대개 그보다 일찍 끝나며, 한 회차에 줄어든 간선이 하나도 없으면 그 뒤로도 줄지 않으므로 멈춰도 됩니다.

V − 1회차를 다 돌고 한 번 더 훑었을 때도 줄어드는 간선이 있으면 음수 순환입니다. 한 바퀴 돌 때마다 총 길이가 짧아지는 고리가 있다는 뜻이라, 무한히 돌면 거리가 −∞로 발산합니다. 그때는 «최단경로»라는 것 자체가 정의되지 않습니다.

아닙니다. 그 순환에서 갈 수 없는 정점의 거리는 여전히 정확합니다. 이 도구는 음수 순환에서 도달할 수 있는 정점만 −∞로 표시하고 나머지는 값을 그대로 보여 줍니다. 시작 정점에서 음수 순환에 아예 닿을 수 없으면 경고조차 뜨지 않습니다.

최종 답에는 영향이 없지만 필요한 회차 수는 달라집니다. 경로를 따라가는 순서로 적으면 한 회차에 거리가 끝까지 퍼지고, 거꾸로 적으면 회차마다 한 칸씩만 퍼집니다. 회차별 표에서 이 차이를 직접 볼 수 있습니다.

전송되지 않습니다. 계산은 전부 브라우저 안에서 이뤄지고, 입력값은 이 브라우저의 localStorage에만 남습니다.