Bellman Ford Algorithm

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

벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 개념 다익스트라 알고리즘이 그리디 알고리즘이였다면, 벨만 포드 알고리즘의 기본 개념은 다이나믹 프로그래밍이다. 즉, 이전에 계산한 최단경로를 이용해 새로운 최단경로를 갱신하는 식으로 동작한다. 예를 들어 시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v사이의 가중치(거리)를 더한 값이다. 위와 같은 그래프가 있다면, s에서 ..