huhsae's day huhsae's day

벨만포드 알고리즘이 글은 GeeksforGeeks의 Bellman–Ford Algorithm | DP-23를 번역한 글입니다. 그래프와 그래프의 source 정점 src를 고려하여, src부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라와 차이점은 그래프의 간선이 음의 값을 가질 수 있다는 점이다. 최단 거리문제는 다익스트라를 활용하여 해결할 수 있다. 다익스트라 알고리즘은 그리디 알고리즘 이며 피보나치 힙을 사용한다면 O(VlogV)의 시간 복잡도를 가졌다. 하지만 다익스트라는 음의 값을 가진 그래프에서는 사용할 수 없으며, 벨만포드를 사용하여야 한다. 벨만포드는 다익스트라보다 간단하며 분산 시스템에 잘 맞다. 하지만 시간 복잡도는 O(VE)로 다익스트라보다 복잡하다.알고리즘Input : 그..