[알고리즘] SSP(2) - 벨만 포드 알고리즘 ( Bellman-Ford Algorithm )

1. 벨만 포드 알고리즘 개요

SSP의 첫 번째 알고리즘인 벨만 포드 알고리즘에 대해 알아보겠습니다.

벨만 포드 알고리즘은 방향 그래프, 음의 가중치를 갖는 그래프에서 SSP를 찾는 것이 목적입니다.

( SSP의 두 번째 알고리즘인 Dijkstra's 알고리즘에서는 음의 가중치를 허용하지 않습니다. )

그런데 간선이 음의 가중치를 갖는 경우, 그리고 그 간선이 순환구조를 띄는 경우 최단 경로를 구할 수 없습니다.

v2 -> v3의 가중치 2보다 v3 -> v2의 가중치 -4가 절대값이 더 크므로, 이 순환구조로 값은 가 되고 따라서도 가 되어 결국 v1 -> v4의 최단 경로는 구할 수가 없게 됩니다.

( 는 최단경로 추정 값, 는 도달할 수 없음을 의미 합니다. )

벨만 포드 알고리즘은 SSP를 구할 수 있음은 물론, 위와 같이 최단경로에 도달할 수 없음을 false를 반환함으로써 표현할 수 있습니다.

이것을 벨만 포드 알고리즘의 정확성이라 합니다.

이제 벨만 포드 알고리즘이 어떻게 동작하는지 살펴보도록 하겠습니다.

2. 벨만 포드 알고리즘

벨만 포드 알고리즘은 정점의 개수만큼 모든 간선을 Relax하는 작업을 수행합니다.

예상할 수 있듯이 지금까지 살펴본 알고리즘에 비해서 시간복잡도가 굉장히 오래 걸린다는 것을 알 수 있습니다.

이렇게 비효율적으로 수행하는 이유는 벨만 포드 알고리즘의 정확성과 관련이 있습니다.

바로 음의 가중치 순환경로가 존재하는지 확인하기 위함이죠.

음의 가중치 순환경로가 존재하면 false를 반환합니다.

Relax의 코드는 아래의 사진과 같으며 바로 벨만 포드 알고리즘의 수행과정을 살펴보도록 하겠습니다.

그래프의 초기 모습입니다.

첫 정점 v1을 제외한 나머지 정점의 값은 로 할당합니다.

벨만 포드 알고리즘은 모든 간선들을 Relax해야 합니다.

Relax하는 간선들의 순서는 구현하기 나름입니다.

이므로

Relax 결과  으로 업데이트 됩니다.

Step 2와 같은 방식으로 Relax 결과 로 업데이트 합니다.

( v2 , v3 ) , ( v3 , v2 )를 음의 순환구조라고 생각할 수 있는데,

이 순환구조는 음의 순환구조가 아닙니다.

5가 -2보다 절대값이 더 크기 때문에 순환이 되더라도 항상 양의 값을 갖게 됩니다.

정점 v1에 대해 모든 간선을 Relax를 했습니다.

이제 다음 정점을 선택하여 또 모든 간선을 Relax를 수행할 것입니다.

Step 4에서 이므로 

Relax 결과 으로 업데이트 합니다.

Bellman-Ford 알고리즘은 정점의 개수만큼 모든 간선을 Relax하기 때문에 엄청난 연산이 수행됩니다.

그러나 덕분에 음의 가중치가 있는 그래프의 단일 출발지 최단경로를 구할 수 있고, 그래프가 음의 순환구조를 갖는다면 이를 식별할 수 있습니다.

같은 SSP 알고리즘인 Dijkstra's 알고리즘은 음의 가중치를 갖는 간선에 대해 SSP를 구할 수 없습니다.

2. 수도코드

1) line 1

그래프를 초기화 합니다.

처음 시작할 정점을 제외한 모든 정점의 값을 로 할당하고, 처음 시작할 정점의  값은 0으로 할당합니다.

2) line 2 ~ 4

정점의 개수만큼 반복문을 돌면서, 모든 간선에 대해 Relax를 수행합니다.

( 위의 동작 과정은 편의상 이해를 돕기위해 마구잡이로 간선을 선택했습니다. )

3) line 5 ~ 8

음의 가중치를 갖는 순환경로가 존재하는지 확인합니다.

존재한다면 false를 반환하고, 존재하지 않으면 벨만 포드 알고리즘이 잘 작동했다는 true를 반환합니다.

( 실제로 음의 순환구조가 되도록 가중치를 변경해보시면 수도코드가 이해가 되실겁니다. )

4) 시간 복잡도

초기화 하는 작업은 의 시간이 걸리고, 음의 순환구조를 검사하는 반복문은 의 시간이 걸립니다.

line 2 ~ 4는 번에 대해 총 번의 Relax를 수행하므로 

이상으로 벨만 포드 알고리즘에 대해 알아보았습니다.

벨만 포드 알고리즘은 정점의 개수만큼 모든 간선에 대해 Relax를 수행하기 때문에 연산량이 엄청납니다.

그러나 이렇게 구현함으로써 음의 가중치를 갖는 그래프에서 SSP를 구할 수 있습니다.