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

벨만 포드는 최단 경로 알고리즘입니다.
하나의 특정 도시에서 다른 도시들로 가는 최단 경로, 최소비용을 구하는데 사용됩니다.

---

벨만 포드 알고리즘과 다익스트라 알고리즘의 차이는 간선에 음수가 있을 때 사용할 수 있는가입니다.
다익스트라 알고리즘은 간선에 음수가 있을 때 사용할 수 없습니다. (참고)
벨만 포드 알고리즘은 "최단 경로는 최대 V-1 개의 간선을 지난다."를 이용한 방법으로 간선에 음수가 있을 때도 사용할 수 있습니다. (정점을 한 번씩 지났을 때가 최대로 많은 간선을 지니는 최단 경로)

그런데 만약 최단 경로에 음수 사이클(가중치의 합이 음수여서 해당 사이클을 돌 때마다 가중치 합이 줄어드는 구간)이 존재한다면 최단 거리는 끊임없이 작아질 것입니다.
그래서 벨만 포드에서 V-1 번 간선들을 탐색하여 최단 거리를 갱신한 뒤 다시 한 번 간선들을 탐색, 최단 거리를 갱신하게 됩니다. 이때 갱신되는 최단 거리가 있다면 이는 음수 사이클이 있다는 것을 의미합니다.

---

도시 i에서 j로 가는 비용이 Wi->j이고 도시로 가는 최소비용을 배열 dist에 저장한다고 했을 때,
벨만 포드 알고리즘은 다음과 같습니다.

1. 시작 도시의 최소비용을 0으로 갱신합니다.(dist[start] = 0, dist 배열 default값은 무한대)
2. 현재 도시(now)를 거쳐 갈 수 있는 도시(next)들의 비용이 현재 저장되어 있는 비용(dist[next])보다 큰 경우 이를 갱신합니다.
[ dist[next] > dist[now] + Wnow->next  =>  dist[next] = dist[now] + Wnow->next ]
3. 2번을 dist값이 갱신된적이 있는 모든 도시(정점)에서 반복합니다.(dist[now]가 무한대가 아닌경우)
4. 2~3번을 V - 1번 반복합니다.
5. 음수 사이클 판별시, 2~3을 한 번 더 반복하여 이때 dist 값이 갱신된다면 음수 사이클이 있음을 의미합니다.

정점의 개수를 V, 간선의 개수를 E라고 했을 때, 벨만 포드는 총 V-1 번 모든 간선들을 탐색합니다.
따라서 시간 복잡도는 O(VE)가 됩니다.

---

최단 경로 알고리즘을 이용하는 문제입니다.
타임머신 (11657) : https://www.acmicpc.net/problem/11657

---

소스 코드 : https://github.com/fpdjsns/Algorithm/blob/master/tip/%EB%B2%A8%EB%A7%8C%ED%8F%AC%EB%93%9C.cpp