벨만 포드 최단 경로 알고리즘

이 문제는 간선이 음수가 될 수 있다는 조건을 제외하면 일반적인 다익스트라 알고리즘과 같은 조건이다

 

 

 

 

(음수 간선)
2번 노드 : 2 + 1 + (-2) = 1
6번 노드 : 2 + 1 + (-2) + 2 + 2 = 5

 

 

 

(음수 간선 사이클)
음수 간선의 순환이 포함되는 경우에는 최소비용을 특정한 값으로 결정할 수 없는 경우가 발생할 수 있다
밑에 예시에서는 음수 간선의 사이클이 발생한다

이때 싸이클에 포함되어 있는 모든 간선에 대한 값을 모두 더하면 음수의 값이 나온다
이 경우에는 싸이클을 반복적으로 도는 과정을 통해서 비용을 무한히 줄일 수 있다

그래서 그래프 내에 음수 간선의 순환이 포함되어 있다면, 최소비용, 즉 최단거리가 음의 무한인 노드가 발생한다

-4 + 2 + 1 = -2
-2 + (-2) + (-2) + ... = - 무한대

 

 

 

특정한 그래프에서 최단 거리를 찾을 때 음수 순환이 포함되어 있는지를 체크하고자 한다면 

벨만 포드 최단 경로 알고리즘을 사용할 수 있다

벨만 포드 알고리즘의 시간 복잡도는 O(VE)로 (V : 정점의 개수) (E : 간선의 개수), 다익스트라 알고리즘에 비해 
느리다

 

 

 

다익스트라 알고리즘은 3번 과정을 N-1번 반복하지만 모든 간선 E개를 다 확인하지는 않고

특정 노드에 붙어 있는 간선만 확인한다
즉, 다익스트라 알고리즘은 벨만 포드 알고리즘보다 더 적은 간선을 체크한다

 

벨만 포드 알고리즘이 기본적으로 다익스트라 알고리즘에 상위 호환이다라는 뜻이다 
벨만 포드 알고리즘은 다익스트라 알고리즘보다 상위 호환이지만 시간복잡도는 더 크다