13-1 벨만-포드 알고리즘

1. 벨만-포드 알고리즘

① 다익스트라, 플로이드 와샬, 벨만 포드 알고리즘

 - 세가지 알고리즘은 모두 최단경로 찾는데 사용되고 유용

 - 주로 많이 사용하는 것은 다익스트라 알고리즘

 

② 벨만-포드 알고리즘

- 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘

- 입력 그래프 G=(V,E)에서 간선의 가중치가 음의 값을 허용하는 임의의 실수인 경우 최단 경로 알고리즘

- 다익스트라는 우선 순위 큐를 사용하여 연결된 가장 가까운 정점을 이용하여 정점의 거리를 갱신했다면,

벨만-포드는 모든 간선을 여러 번 확인하여 최단 거리를 갱신한다.

- 벨만 - 포드 알고리즘은 가중치가 음수인 경우도 허용하지만, 음수 가중치가 사이클을 이루고 있는 경우 작동하지 않음.

 

③ 벨만- 포드 알고리즘에 대한 전제조건

- 최단 경로는 사이클을 포함할 수 없기 때문에, 최대 |V|-1개의 간선만 사용 가능

- 최단 거리가 갱신되는 노드가 없어질 때까지 계속해서 반복하여 구해주고, 음의 가중치로 인한 갱신을 무한히 하게 되는 경우 탈출시켜야함(무한히 반복될 때 최단 거리 없다고 함)

 

2. 벨만-포드 알고리즘 적용방법

①  동작 원리

 

3. 벨만-포드 알고리즘 적용 예

①  예시