벨만-포드 알고리즘

벨만 포드 알고리즘

• 벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘

• 다익스트라 알고리즘과 다르게 음수 가중치가 있는 그래프에서도 최단 거리를 구할 수 있다

• 단, 다익스트라 알고리즘은 시간복잡도가 O(ElogV)인데 비해, O(VE)로 느리다.

다익스트라 알고리즘 vs 벨만-포드 알고리즘

다익스트라	벨만포드
매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 방문하여 한 단계씩 최단 거리를 구해나간다 (그리디)	매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다.
음수 간선이 있는 경우를 제외하면 최적의 해를 찾을 수 있다	음수 간선이 있는 경우에도 최적의 해를 찾을 수 있다.
시간복잡도가 O(ELogV)	시간복잡도가 O(VE)

• 즉 모든 간선의 비용이 양수면 다익스트라, 음수 간선이 포함되어 있으면 벨만-포드를 사용하면 된다.

알고리즘 진행 과정

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 다음 과정을 (V-1)번 반복한다.
   1. 모든 간선 E를 하나씩 확인한다.
      • 이 때, 간선을 탐색하는 순서는 상관이 없으나, 한 간선에 대해 dist값이 INF가 아닌 정점이 연결된 경우에만 해당 간선을 탐색해야 한다.
   2. 각 간선을 거쳐 다른 노드로 가능 비용을 계산하여 최단 거리 테이블을 갱신한다.
   • 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3번 과정을 1번 더 수행한다.
     • 이 때 만약 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

       

출처

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

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?

https://velog.io/@kimdukbae/알고리즘-벨만-포드-알고리즘-Bellman-Ford-Algorithm

Uploaded by N2T