알고리즘에서 '벨만-포드(Bellman-Ford)' 알고리즘이 다익스트라와 비교했을 때 가지는 특징은?

해설

벨만-포드는 모든 간선을 V-1번 반복하여 완화(relaxation)합니다. O(VE)로 다익스트라의 O((V+E)logV)보다 느리지만, 음수 가중치를 처리할 수 있습니다. V번째 반복에서도 거리가 갱신되면 음수 사이클이 존재한다는 것을 감지합니다.