벨만-포드(Bellman-Ford)

다익스트라 알고리즘의 단점

벨만-포드 알고리즘은 다익스트라 알고리즘과 유사하다

다익스트라의 단점을 해결하는 알고리즘으로 사용되는데, 그래프의 간선의 가중치에 음수가 존재하는 경우이다

위 그래프에 다익스트라 알고리즘을 적용하면 다음과 같이 진행된다

이때 시작점을 정점 1로 설정한다

정점	1	2	3
최단 거리	0	INF	INF
방문여부	False	False	False

거리 값이 가장 적은 1의 인접 정점까지의 거리를 계산한다

정점	1	2	3
최단 거리	0	20	10
방문여부	True	False	False

방문하지않은 정점 중 거리 값이 가장 적은 정점을 선택한다

이때는 3을 선택한다

정점	1	2	3
최단 거리	0	20	10
방문여부	True	False	True

3을 선택했을 때 나아갈 정점이 없으므로 곧바로 남은 2를 선택한다

그러나 정점 2 외에 모든 정점을 이미 방문했으므로 다익스트라 알고리즘이 종료된다

정점	1	2	3
최단 거리	0	20	10
방문여부	True	True	True

결국 위와 같은 테이블이 완성되지만 오답이 된다

올바른 최단 경로는 다음과 같다

정점	1	2	3
최단 거리	0	20	5

3은 1 → 2 (20) 에서 2 → 3 (-15) 를 거치면 5가 되기 때문이다

따라서, 다익스트라는 최단 경로 값이 가장 적은 정점부터 선택하는 이유때문에 음의 가중치가 무시되는 것이다

벨만-포드 알고리즘

벨만-포드 알고리즘은 음의 가중치인 간선을 확인하기 위해 모든 간선을 확인하는 방식으로 진행된다

전체 진행방식은 다음과 같다

1. 시작점을 지정하고, 시작점의 최단거리를 0으로 초기화

2. 모든 간선을 검사

3. 2의 과정 중에 시작 정점(s)에서 도착 정점(e) 까지 가는 거리가 기존 e의 거리 값보다 작으면 e의 거리 값을 갱신

4. 2~3의 과정을 정점의 개(V)-1번 반복

여기서 의문점이 생길 수 있다

4의 과정에서 왜 반복을 V-1번 반복해야할까? 더 많이, 혹은 더 적게해도 되지 않을까?

반복을 얼마나 해야할지 잘 모르겠는데 효율적으로 연산을 줄이기 위해, 최악의 경우에서 필요한 연산은 상한이 됨을 생각함으로써 이 의문을 해결할 수 있다

먼저 최단 경로에 필요한 최대 간선의 개수는 V-1개이다

그리고 2번 과정을 거칠 때마다 최소 1개 이상의 정점이 갱신됨을 보장한다

1번째 반복일 때는 검사하는 간선이 시작점부터가 아닌 가장 먼 곳부터라고 한다면,
무한대 값이기 때문에 더 작은 값으로 갱신된다 하더라도 의미는 없다

그리고 시작점과 연결된 간선을 가장 나중에 검사하게 되면 최소 1개의 정점이 갱신될 것 이다

즉, 최악의 경우 매 반복마다 서로 다른 1개의 정점이 갱신되는 것이다

따라서 시작점을 제외한 나머지 정점은 적어도 V-1번의 반복을 거치면 모두 갱신이 된다!

이런 이유로 V-1번의 반복을 통해 모든 정점의 갱신을 완료할 수 있는 것이다

음수 사이클 문제

그래프에서는 최단 경로를 찾는데 사이클 문제를 무시할 수 없다

특히 벨만-포드 알고리즘의 경우 더욱 부각된다

1번 정점은 초기엔 2의 값을 가지는데, 1 → 2 → 3 → 1 → 2 → .. 를 통해 무한하게 1의 최단 거리 값이 작아질 수 있다 ( 2 + (3 - 4 - 1) + (3 - 4 - 1) + ... )

그리고 위에서 V-1번의 반복을 통해 모든 정점의 갱신이 완료된다는 것을 알았기 때문에, V-1번의 반복 이후에 더 이상 모든 간선을 검사해도 각 정점은 갱신되지 않아야 한다.

따라서 위와 같은 문제를 해결하기위해 벨만-포드 알고리즘에 조건을 추가한다

V-1번을 반복하고 한 번 더 반복할 때, 갱신이 이루어지면, 음수 사이클이 존재한다는 것이다

시간복잡도

벨만-포드 알고리즘에서 음수 사이클을 모두 고려하는 것 까지하여, 정점의 개수 V번 동안 간선의 개수 E개를 모두 검사하기 때문에 2중 반복문이 된다

따라서 벨만-포드 알고리즘의 시간복잡도는 $O(VE)$가 된다

벨만-포드 알고리즘으로 음수 가중치가 없는 그래프를 순회해도 모든 간선을 검사하기 때문에, 최단 경로를 찾을 수는 있다

다만 음수 가중치가 없는 그래프에 한정하여 다익스트라 알고리즘이 $O(ElogV)$로 훨씬 빠르므로, 이 경우에는 다익스트라를 채택하는 것이 낫다