벨만-포드(Bellman-Ford) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다. (단일 출발)모든 경우의 수를 고려하기 때문에, 다익스트라 알고리즘보다 시간복잡도가 높다.그렇지만 다익스트라 알고리즘과 달리 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 알고리즘 동작 방식매 단계(cycle)마다 모든 노드(vertex)를 방문한다.하나의 노드를 방문할 때마다 이 노드와 인접한 다른 노드들을 확인하여, 최단 거리 테이블을 갱신한다. 단계는 최단 거리 테이블이 더이상 업데이트되지 않을 때까지, 최대 V-1번 반복된다. (V: vertex, 노드의 수)만일 V-1번의 단계를 거친 이후에도 최단 거리 테이블이 업데이트 된다면, 이는 음수 사이..