벨만포드 알고리즘

최단거리 알고리즘 중 하나

1. 하나의 정점에서 다른 정점까지의 최단거리를 알 수 있다

2. 최단경로는 d(s, u) = min(d(s, u), d(s, u) + w(u, v))로 지속적으로 검사하게 된다

3. 정점과 정점사이의 최단거리 정점은 최대 V-2개만 허용하고 이를 잇는 최단거리 간선또한 V-1만 허용하게 된다. 따라서 두 정점 사이의 최대 V-1개의 간선을 조사해야므로 시간복잡도는 O(VE)가 된다

 

쉽게 말해

V-2번에 도달한 정점에서 V-1번만에 도달해야하는 정점이 최단거리라면

V-1번만에 거리를 측정할 수 있는 정점은 그 전에는 계속 INF로 초기화 되어 있다