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

최단 경로 알고리즘은 크게 두 가지로 분류된다.

1. one-to-all : 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다. (다익스트라 알고리즘, 벨만-포드 알고리즘)
2. all-to-all : 모든 정점에 대해 자신을 제외한 다른 모든 정점으로의 최단 경로를 구한다. (플로이드-와샬 알고리즘)

 

벨만 포드 알고리즘은 one-to-all에 속하며, 이 외에도 다익스트라 알고리즘이 있다.

 

 

 

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

---

벨만 포드 알고리즘의 특징은 다음과 같다.

1. one-to-all (하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다.)
2. 음의 가중치일 경우에도 사용이 가능하다. (다익스트라는 가중치가 음수이면 사용이 불가능)
3. 시간 복잡도가 $\mathcal{O}(V \cdot E)$로 다익스트라보다는 느리다.

 

 

 

 

참고자료

---

[1] m.blog.naver.com/kks227/220796963742