가중 그래프 최단 경로
음수가 아닌 방향 그래프에서 경로와 도달 거리를 확인하세요.
예시값이 입력되어 있습니다. 바로 확인하거나 값을 바꿔 보세요.
입력은 브라우저에서 처리합니다. 새로고침하면 예시값으로 돌아갑니다.
사용 방법과 예시
d(v)=min(d(v),d(u)+w(u,v))
기본 그래프는 A→C→B→D를 따라 총 가중치 4에 도달합니다.
노드 30개·간선 100개 이하이며 음수 간선은 지원하지 않습니다.
자주 묻는 질문
최단 경로에서 반대 방향도 자동 연결되나요?
아니요. 유향 간선입니다. 양방향 연결에는 역방향 간선도 입력해야 합니다.
도착점에 도달하지 못하면 어떤 결과인가요?
경로 없음과 무한 거리를 표시합니다. 연결되지 않은 것을 거리 0으로 처리하지 않습니다.
계산 기준과 참고 자료
- Princeton Algorithms: Shortest Paths
d(v)=min(d(v),d(u)+w(u,v))