벨만-포드 최단경로 시각화
음수 가중치가 있는 그래프에서 최단 경로를 찾고 음수 사이클을 검출하는 알고리즘을 학습합니다
그래프★★☆
속도
1 / 1반복 횟수: 0 / 1이완 횟수: 0
출발점:
출발점 갱신됨 검사 중 음수 간선/사이클
벨만-포드가 V-1번 반복하며 모든 간선을 이완하는 과정을 관찰하세요.
벨만-포드가 V-1번 반복하며 모든 간선을 이완하는 과정을 관찰하세요.
벨만-포드 알고리즘이란?
벨만-포드(Bellman-Ford) 알고리즘은 단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다익스트라와 달리 음수 가중치 간선을 허용하며, 음수 사이클을 검출할 수 있습니다. V-1번의 반복에서 모든 간선을 이완(Relaxation)하는 방식으로 동작합니다.
사용 방법
- 1새 그래프 버튼으로 방향 가중치 그래프를 생성하세요
- 2음수 가중치 허용 체크박스로 음수 간선을 포함할 수 있습니다
- 3출발점 드롭다운으로 시작 노드를 변경하세요
- 4노드 아래 배지는 출발점에서의 현재 최단 거리입니다
- 5빨간색 간선은 음수 가중치를 나타냅니다
학습 팁
- •다익스트라는 음수 가중치에서 실패하지만, 벨만-포드는 정확합니다
- •V-1번 반복 후에도 갱신이 일어나면 음수 사이클이 존재합니다
- •시간 복잡도 O(VE)로 다익스트라의 O(E log V)보다 느립니다
- •SPFA는 벨만-포드의 큐 최적화 버전입니다
자주 묻는 질문
Q. 벨만-포드 vs 다익스트라, 언제 어떤 것을 쓰나요?
A. 다익스트라: 음수 간선이 없을 때 더 빠릅니다(O(E log V)). 벨만-포드: 음수 간선이 있거나 음수 사이클 검출이 필요할 때 사용합니다(O(VE)). 분산 라우팅 프로토콜(RIP)에서는 벨만-포드 변형이 사용됩니다.
Q. 왜 V-1번 반복하나요?
A. 최단 경로는 최대 V-1개의 간선을 포함합니다. 각 반복에서 최소 하나의 간선이 올바른 최단 거리를 확정하므로, V-1번이면 모든 최단 경로가 결정됩니다.