[알고리즘/이론] 벨만-포드 알고리즘

벨만-포드 알고리즘

벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 출발점에서 도달가능한 음의 순환의 존재 여부를 확인할 수도 있습니다. 음의 순환이 존재하면 최단거리는 구할 수 없습니다.

---

모든 최단경로는 순환을 가지지 않으며 따라서 한 정점을 두 번 이상 방문하지 않습니다. 그래프에 정점이 V개 있다면 최단 경로는 최대 V-1개의 간선을 가질 수 있습니다. 최단거리 계산에는 출발점에서 도착점까지의 경로를 순서대로 완화함으로써 최단거리 값을 구할 수 있다는 정리가 이용됩니다. 그래프의 모든 간선을 V-1번 완화(노드의 추정최단거리 값을 갱신하는 행위)하면 한 출발점에서의 모든 다른 노드까지로의 최단거리 값을 구할 수 있다는 사실을 알 수 있습니다.

---

음의 순환을 확인하는 방법은 최종적으로 구해진 최단거리 값이 삼각부등식의 특성 만족 여부를 검사하는 것입니다. 음의 순환의 경우 V-1번 완화에 의해 최단 거리 값이 비정상적으로 작아지기 때문에 최단거리 값과 간선의 값이 삼각부등식을 만족시키지 못합니다. 따라서 이를 통해 음의 순환 존재 여부를 판단할 수 있습니다.