KalelPark's LAB

Bellman-Ford Algorithm 이란? 한 정점(Vertex)에서 다른 정점(Vertex)까지의 최단 거리를 구하는 알고리즘이다. 다익스트라(Dijkstra Algorithm)과 달리, 정점(Vertex) 간의 간선(edge) 비용이 음수인 경우에도 사용가능하다. 벨만 포드(Bellman-Ford)는 다이나믹 프로그래밍(Dynamic Programming)이라고도 할 수 있다. 그러한 이유는 매번 저장해놓은 최소 비용을 활용해서, 새로운 최소 비용을 갱신하기 때문이다. 벨만 포드(Bellman-Ford)는 다익스트라(Dijkstra Algorithm)보다 시간이 오래 걸리는데, 그러한 이유는 최소 비용을 가지는 간선(edge)만을 우선적으로 뽑는 다익스트라(Dijkstra Algorithm) 달..