최단 경로

a -> b 의 최단 경로는 정점의 개수를 n이라고 했을 때, 최대 n-1 개의 간선으로 이루어져 있다.

벨만포드

from -> to (cost)
dist[i] = 시작점에서 i 로 가는 최단 경로

• 1. 모든 간선 e (from ,to, cost) 에 대해서 다음을 검사한다.
     dist[to] = min (dist[to], dist[from] + cost);

• 1번 과정을 총 N-1 번 반복한다.

• 시간 복잡도 : O(VE)
  E <= V^2 이기 때문에 O(V^3) 이 된다.

• 가중치가 음수인 경우에도 사용할 수 있다.

벨만 포드는 빠른 알고리즘이 아니라서, 잘 사용하진 않지만, 유일하게 가중치가 음수일때 구할 수 있는 최단 경로 알고리즘 이라서 이런 경우에는 벨만포드를 사용해야 한다. !!

음수 사이클

n-1 번 간선 돈거하고, n 번 간선 돈거하고 결과가 같아야 하는데, 만약에 다르다는 것은 최단 경로가 존재하지 않는 음수 사이클이 존재한다고 할 수 있다.

https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/