다익스트라 최단경로 계산기

아직 확정하지 않은 정점 가운데 시작점에서 가장 가까운 것을 하나 골라 확정하고, 그 정점을 거쳐 가면 더 가까워지는 이웃의 거리를 줄이는 일(완화)을 되풀이합니다. 한 번 확정한 정점은 다시 보지 않는데, 가중치가 음수가 아니면 그 거리가 더 줄어들 여지가 없기 때문입니다.

«한 번 확정한 거리는 더 줄지 않는다»는 전제가 깨지기 때문입니다. 먼 정점을 거쳐 가는 길이 음수 간선을 만나 더 짧아질 수 있는데, 이미 확정한 정점은 다시 보지 않으므로 그 길을 놓칩니다. 순서에 따라 우연히 맞기도 하지만 맞았는지 아닌지를 다익스트라만으로는 알 수 없어, 이 도구는 값을 내되 경고를 함께 띄웁니다.

벨만-포드 알고리즘을 씁니다. 모든 간선을 정점 수만큼 훑어 거리를 줄이는 방식이라 느리지만 음수 간선이 있어도 정확합니다. 다만 음수 순환(돌 때마다 총 길이가 짧아지는 고리)이 있으면 최단경로 자체가 정의되지 않으며, 벨만-포드는 그런 순환이 있다는 것을 알려 줄 수 있습니다.

시작 정점에서 갈 길이 아예 없는 정점입니다. 간선에 방향이 있으면 한쪽으로만 갈 수 있어 이런 정점이 자주 생깁니다. 간선 방향을 «없음»으로 바꾸면 닿게 되는 경우도 있습니다.

그중 하나만 보여 줍니다. 거리가 같은 경로가 여럿일 때 어느 것이 나올지는 정점이 확정되는 순서에 달려 있으며, 이 도구는 결과가 재현되도록 «거리가 같으면 이름이 앞선 정점 먼저»로 정해 두었습니다. 어느 경로를 고르든 거리는 같습니다.

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