인생자취

1. 들어가기 지난 글에서는 경로의 가중치가 음이 아닌 수로 부여된 경우에 사용되는 다익스트라 알고리즘에 대해 살펴봤다. 이번 글에서는 경로의 가중치가 음수인 경우에 단일 출발지의 최단 경로 문제를 해결하는 벨만-포드(Bellman-Ford) 알고리즘에 대해 알아볼 것이다. 2. 벨만-포드(Bellman-Ford) 벨만-포드 알고리즘은 출발 점으로부터 도달 가능한 음의 가중치의 순환(음수 사이클)이 존재하는 경우에는 최단경로를 구할 수 없고, 그러한 순환이 없다면 최단 경로들과 그 경로들의 가중치를 계산할 수 있다. 벨만-포드 알고리즘은 매번 모든 간선을 확인하므로 다익스트라 알고리즘보다는 느리다. 시간 복잡도는 O(VE); E는 경로(간선) 수, V는 꼭짓점(노드)의 수 이다. 하지만 간선이 음수로 존..