Shortest path 패널이 푸는 것 Shortest path 패널은 같은 가중 그래프 위에서 네 알고리즘을 실행합니다. Dijkstra, A*, Bellman–Ford, Floyd–Warshall입니다. 각 결과 행 묶음은 방법을 밝히고 거리와 경로를 출력하며, 추적하는 두 단일 소스 탐색에서는 정점이 확정된 순서도 보여 줍니다. 그래프는 공유 그래프 이론 워크벤치 에서 구성하며, Directed 토글, 간선 가중치, 인접 행렬 붙여넣기 상자가 모두 적용됩니다.
각 알고리즘 실행 방법 01 그래프를 불러오고 끝점을 설정합니다. 프리셋을 만들거나 인접 행렬을 붙여넣은 뒤 Source와 Target을 고릅니다. 프리셋 구성은 이들을 첫 번째와 마지막 노드로 재설정합니다. 02 Dijkstra 는 거리, 경로, 확정 순서를 답하고 음수 간선이 있는 그래프를 거부합니다 — 오류는 해당 간선을 지목하고 Bellman–Ford를 가리킵니다. 03 A\ **A***는 휴리스틱 선택기(manhattan / euclidean / zero)를 추가하고, Dijkstra 대비 확장한 노드 수, 실제로 사용한 휴리스틱 스케일, 휴리스틱이 일관적이어서 최적인지를 보고합니다. 04 Bellman–Ford 는 완화 라운드를 보고하고 노드별 최종 거리를 나열하며 음수 사이클이 있으면 표시합니다. 05 Floyd–Warshall 은 한 소스에서 거리 행렬을 채우고, 음수 사이클 노드를 표시하며, 같은 표로 임의의 소스/타깃 쌍에 답할 수 있습니다.
계산 예시 패널에서 읽은 값:
설정
계산 결과
기본 6-노드 그래프, Dijkstra A → F
거리 13 , 경로 A → C → B → D → E → F , 확정 순서 A → C → B → D → E → F , d[B] 3 , d[C] 2 , d[D] 8 , d[E] 10
Grid 4 × 5, Dijkstra 1-1 → 4-5
거리 7 , 확정 순서는 20 개 노드를 모두 나열, 경로 1-1 → 1-2 → 2-2 → 3-2 → 3-3 → 3-4 → 3-5 → 4-5
기본 그래프, euclidean을 쓴 A*
거리 13 , 같은 경로, 확장 노드 6 / Dijkstra 6 , 휴리스틱 스케일 0.01346 , 일관적 최적 Yes
Negative weights 프리셋, S에서 Bellman–Ford
3 회 완화 라운드, d[S] 0 , d[A] 3 , d[B] 5 , d[C] 0 , d[D] 3 , 음수 사이클 None
Negative weights 프리셋, Floyd–Warshall S → D
거리 3 , 경로 S → B → A → C → D , 음수 사이클 노드 None
Dijkstra의 d[C] = 2 는 직접 간선 A–C에서, d[B] = 3 은 A → C → B에서 나오며, 더 무거운 간선 A–B(가중치 4 )에서 나오지 않습니다. Bellman–Ford는 −3 간선이 있는 그래프에서 같은 값에 도달하고, Floyd–Warshall은 음수 간선과 양수 간선을 연결해 S → B → A → C → D를 찾습니다.
A\*가 스케일을 출력하는 이유 캔버스 좌표와 간선 가중치는 서로 다른 양이므로, A*는 레이아웃에서 휴리스틱을 측정하고 모든 호에서 h(u) ≤ w(u,v) + h(v)를 유지하는 최대 계수로 스케일합니다. 기본 그래프에서 euclidean 스케일은 0.01346 이고, 세 휴리스틱 모두 Dijkstra와 같은 6 개 노드를 확장합니다. 일관적-최적 행은 반환된 거리가 정확하다는 약속입니다.
한계
Dijkstra와 A\*에는 비음수 가중치. 둘 다 너무 큰 거리를 반환하는 대신 음수 간선을 거부합니다. Negative weights 프리셋에는 같은 패널에서 Bellman–Ford로 전환하세요. 실행당 하나의 소스. 다중 소스 Dijkstra도 Johnson 전점대도 없습니다. Floyd–Warshall이 전점대 옵션이며 세제곱 비용입니다. 패널은 파일에서 간선 목록을 읽거나 경로를 내보내지도 않습니다 — 인접 행렬을 워크스페이스에 기록해 matrix tools 로, 가장 저렴한 배선은 Spanning tree 패널로, 용량 질문은 Flow & matching 으로 가져가세요.
음수 간선 경계 Negative weights 프리셋(S → A 4, S → B 5, A → C −3, B → A −2, B → C 4, C → D 3)을 만들고 Source S로 Dijkstra를 누릅니다. 패널은 그럴듯한 잘못된 숫자 대신 "Edge 3 has weight -3. Dijkstra cannot handle negative weights (a settled distance could still be lowered) — use Bellman–Ford instead" 메시지로 거부합니다. 알고리즘을 Bellman–Ford로 바꾸면 S → C가 0 으로 읽히는데, Dijkstra의 탐욕적 확정으로는 결코 만들 수 없는 거리입니다. A*도 같은 거부를 가지며 그 메시지도 Bellman–Ford를 가리킵니다.
활용 사례 투어의 최적성 증명 Dijkstra의 확정 순서는 최종 거리가 옳다는 증명입니다. 각 정점은 한 번 확정되고 다시 방문되지 않습니다. 기본 그래프에서 직접 간선 A–B의 가중치는 4 지만 C를 거치는 경로는 3 이고, 순서 A → C → B → D → E → F 는 C가 B보다 먼저 확정되었음을 보여 줍니다 — 패널이 스스로의 정확성 논증을 보여 주는 것입니다.
휴리스틱을 스케일해야 하는 이유 가르치기 A*를 zero 휴리스틱으로 두면 실행은 부기 작업이 붙은 Dijkstra입니다(스케일 1 ). 배치된 기본 그래프에서 euclidean으로 두면 스케일이 0.01346 으로 떨어져, 경로는 정확하게 유지하면서 추정값이 실제 비용을 넘을 수 없습니다.
계획에서의 음수 비용 Negative weights 프리셋은 두 단계 사이의 크레딧을 모델링합니다. Bellman–Ford는 S → D를 3 으로 답하고, Floyd–Warshall도 같은 값을 확인하며, 어느 쪽도 음수 사이클을 보고하지 않으므로 개선 사슬 S → B → A → C → D는 종료됩니다.
개인정보 그래프 편집과 모든 shortest path 실행은 브라우저에서 이루어지며 아무것도 업로드되지 않습니다.
참고 문헌
Wikipedia, Dijkstra's algorithm , en.wikipedia.org (访问日期:2026-10-07)— 탐욕적 확정과 비음수 가중치.
Wikipedia, Bellman–Ford algorithm , en.wikipedia.org (访问日期:2026-10-07)— 완화 라운드와 음수 사이클 검출.
Wikipedia, Floyd–Warshall algorithm , en.wikipedia.org (访问日期:2026-10-07)— 전점대 동적 계획법.
Wikipedia, A* search algorithm , en.wikipedia.org (访问日期:2026-10-07)— 허용적이고 일관적인 휴리스틱.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4th ed., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— 단일 소스 최단 경로.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07