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

다익스트라 알고리즘은 간선 가중치가 음수가 아닌 그래프에서 한 노드로부터 다른 모든 노드까지의 최단 경로를 찾습니다. 경로 안내, 네트워크 라우팅, 많은 교재 문제의 바탕이 되는 알고리즘입니다. 간선을 목록으로 입력하고 시작 노드(그리고 원하면 도착 노드)를 고르면, 이 계산기가 모든 최단 거리와 경로, 그리고 손으로 추적할 때처럼 어느 노드를 방문하고 어느 거리를 갱신하는지 보여 주는 단계별 표를 만들어 줍니다.

사용 방법

1. 한 줄에 간선 하나씩 출발, 도착, 가중치를 입력합니다(A B 4).
2. 한 방향 간선이면 "방향"을 켜고, 양방향이면 꺼 둡니다.
3. 시작 노드와 (선택 사항인) 도착 노드를 입력합니다.
4. 거리와 경로, 모든 노드의 표, 단계별 과정을 확인합니다.

계산식

반복: 방문하지 않은 노드 중 d(u)가 가장 작은 u를 방문 · u → v 간선(가중치 w)마다 d(u) + w < d(v)이면 d(v) = d(u) + w, prev(v) = u

시작 노드(0)를 제외한 모든 거리는 ∞에서 시작합니다. 노드를 방문하면 그 거리가 확정되는데, 이는 가중치가 음수가 아닐 때만 보장되므로 음수 가중치는 거부합니다(벨만–포드가 처리). 경로는 prev를 따라 시작 노드까지 거슬러 올라가 복원합니다. 동점이면 먼저 적은 노드가 우선합니다. 평행 간선도 허용되며 더 싼 쪽이 선택됩니다.

예시

샘플은 『Introduction to Algorithms』(CLRS) 그림 24.6의 방향 그래프입니다. s에서 출발하면 방문 순서는 s(0), y(5), z(7), t(8), x(9)입니다. x까지의 최단 경로는 s → y → t → x, 길이 9(5 + 3 + 1)입니다. 직행처럼 보이는 s → t 간선(10)은 s → y → t(8)에 집니다.