Dijkstra Algorithm / Bellman Ford Algorithm / Floyd Warshall Algorithm

Single source shortest path를 찾는 방법인 Dijkstra Algoritm, Bellmanfor Algorithm, 그리고 All pair shortest path를 찾는 방법인 Floyd Warshall Algoritm에 대해 알아보자.

Dijkstra Algorithm

시작점에서부터 거리가 가까운(d[v]가 작은) vertex들을 차례로 선택하면서 d[v]를 조정(?) 하는 알고리즘.

if (d[u] + c[u,v] < d[v])
d[v] = d[u] + c[u,v]

식으로 써보면 짜증나게 생겼지만 정작 그림으로 이해하면 별로 어려운 개념은 아니다.

Dijkstra는 c[u,v]가 음수인 graph 에서는 사용할 수 없다.

Bellman Ford Algorithm

Dijkstra랑 원리는 같은데 조정 과정을 n-1번(여기서 n은 vertex의 개수) 수행하는 알고리즘.
Dijkstra랑 다르게 c[u,v]가 음수여도 사용 가능하지만 cycle이 존재하는 graph에서 cycle을 구성하는 c[u,v]의 합이 음수가 되는 경우 사용할 수 없다.

Floyd Warshall Algorithm

설명하기가 매우 귀찮다...

제대로 알고싶으면 갓갓 제니센세의 강의를 듣도록 하자(무책임).
https://www.youtube.com/watch?v=Gc4mWrmJBsw