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

1. 개념

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘.

다익스트라 알고리즘과는 다르게 음의 가중치를 가지는 간선이 있어도 가능하다.

또한, 그래프에 음의 가중치를 가진 사이클의 존재 여부를 확인할 수 있다.

2. 구현

V개의 정점과 E개의 간선을 가진 가중 그래프에서 어떤 정점 A에서 B까지의 최단거리는

최대 V-1개의 간선을 사용한다는 아이디어로 시작한다.

    1) Distance[i] : 출발점(S)에서부터 i 정점까지의 최단거리를 저장하는 배열. Distance[S] = 0 으로 초기화하고, 나머지는 모두 무한대로 초기화

    2) V-1 번 모든 간선을 확인해 아래의 조건을 만족할 때마다 최단거리배열을 갱신한다.

      - 어떤 간선 E = (I,J,W)에 대해서 가중치를 W라고 할 때, D[I]가 무한대가 아니고, D[J] > D[I] + W 이면 이 값으로 업데이트해준다.

    3) V번째 모든 간선을 확인했을 때 거리배열이 갱신되었다면 그래프 G는 음의 사이클을 가지는 그래프이다.

최단거리를 구하기 위해 V-1번 E개의 간선을 확인하므로 O(VE) 이다.

[벨만포드 예제 : http://gyutts.tistory.com/168]