[알고리즘] 벨만포드 알고리즘

벨만-포드 알고리즘이란?

한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다.

 

다익스트라 알고리즘과의 비교

다익스트라 알고리즘은 양수일 때에만 사용이 가능하지만, 벨만포드 알고리즘은 음수에서도 사용이 가능하다.

시간 복잡도는 다익스트라 알고리즘이 더 효율적이다.

 

벨만포드 알고리즘

1. 시작 노드를 설정한다.

2. 시작 노드를 제외한 모든 노드의 거리를 INF로 구성한다.

3. 현재 노드의 모든 인접 노드를 탐색하며 기존의 연결 관계보다 현재 노드를 거치고 가는 것이 더 짧을 경우 갱신한다.

4. 모든 노드에 대해 반복한다.

5. 모든 노드에 대해 반복하고 나서도 갱신된다면, 그건 음수 사이클이 존재한다는 의미이다.

 

벨만포드 알고리즘 예시

1.노드 A에서부터 시작한다. 2 < INF, 4 < INF이므로 비용을 업데이트한다.

 

2. 노드 B에 대해서도 계산해본다. 3 < 4이므로 C까지의 거리를 3으로 바꾸고, D까지의 거리는 2-3 = -1 < INF로 -1을 저장한다.

3. 8 < INF이므로 E까지의 비용을 8로 바꾼다. D까지의 비용 3+3 =6은 -1보다 크므로 업데이트하지 않는다.

4. D에서 E까지의 비용이 더 싸다. -1-2 = -3 < 8이므로 비용을 업데이트한다.

 

사이클 설명을 위해 E -> D의 경로를 비용이 1인 것으로 만들어봤다.

이미 방문을 한 D의 사이클이 새로 갱신되었다. 이는 음의 사이클이 생긴다는 뜻이다.