[알고리즘] 벨만-포드알고리즘 : 음의 간선이 존재할 때 최단거리 구하기

Bellan-Ford Algorithm

 

용도 : 한 정점에서 다른 모든 정점으로 가는 최단거리를 구할 때 이용할 수 있다.

조건 :  음의 간선이 존재하고, 음의 사이클을 안가지며, 시간복잡도 O(VE)를 감당할 수 있는경우

위 경우가 아닌경우에는, 다른 최단거리알고리즘을 고려해보자.

 

 

원리 : 모든 간선에 대해, 정점수-1만큼 반복해서 조회하면서 갱신하자

1. 시작은 다음과 같이 최단거리 테이블을 세팅하는것으로 시작한다. 내가 시작하는 정점의 최단거리값을 0으로 세팅한다

2. 모든 간선을 돌면서, 최단거리를 갱신한다.

3. 2의 과정을 V-1번 반복한다.*

4. 만약 V번째 2의과정을 반복했을때, 갱신되는 값이 존재한다면, 음의 사이클이 존재함을 알 수 있다.

 

 

*V-1 번 반복하는이유

0번노드에서 다른 노드로의 최단거리를 구할때, 다음과 같은 최악의 상황을 고려해보자.

0 -> 1 -> 2 -> 3  -> 4

그리고, 간선리스트가 다음 순서로 들어왔다고 생각해보자.

3->4

2->3

1->2

0->1

이 경우, 모든 정점으로의 최단거리를 구하려면, 최소 V-1번 반복해야함을 알 수 있다.