Bellman-Ford1 벨만포드 알고리즘 (Bellman-Ford algorithm) 벨만 포드는 최단 경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로 가는 최단 경로, 최소비용을 구하는데 사용됩니다. 벨만 포드 알고리즘과 다익스트라 알고리즘의 차이는 간선에 음수가 있을 때 사용할 수 있는가입니다. 다익스트라 알고리즘은 간선에 음수가 있을 때 사용할 수 없습니다. (참고) 벨만 포드 알고리즘은 "최단 경로는 최대 V-1 개의 간선을 지난다."를 이용한 방법으로 간선에 음수가 있을 때도 사용할 수 있습니다. (정점을 한 번씩 지났을 때가 최대로 많은 간선을 지니는 최단 경로) 그런데 만약 최단 경로에 음수 사이클(가중치의 합이 음수여서 해당 사이클을 돌 때마다 가중치 합이 줄어드는 구간)이 존재한다면 최단 거리는 끊임없이 작아질 것입니다. 그래서 벨만 포드에서 V-1 번 간선들을 .. 2019. 9. 26. 이전 1 다음