벨만-포드

[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘

Bellman-Ford Idea 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 단, 음의 사이클이 없는 그래프에서만 벨만-포드 알고리즘을 적용할 수 있습니다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 벨만-포드 알고리즘은 이 중 2..