벨만 포드 알고리즘, 플로이드 알고리즘.

잘 설명된 블로그 : http://kks227.blog.me/220796029558 (알고리즘 설명이 진짜 잘 되있네요)

앞의 다익스트라 알고리즘은 a에서 b로 갈때 가중치가 음수가 아니라고 가정한 상태에서 코딩을 한다.

하지만 이 벨만 포드 알고리즘으로 가중치가 음수일 경우까지 판별이 가능하다.

음수 검사까지 하므로 시간복잡도는 늘어나서 O(VE)이다.

사진은 역시 저 블로그에서 가져왔다.

0에서 2까지 가는 최소거리를 찾을때 다익스트라 알고리즘은 음수가 아니라고 가정한 상태이므로

8로 최소값을 잡는다. 그런데 진짜 최소거리는 1을 거쳐서 가는 5다. 이러한 음수판별까지하는게 

벨만 포드 알고리즘이다.

그런데 음의 가중치가 있는 그래프를 판별시 항상 무한대 사이클을 염두해 두어야 한다.

이 무한대 사이클을 판별하기 위해 추가 코딩이 필요하다.

역시 자세한 내용은 위의 블로그 참조 : http://kks227.blog.me/220796029558

플로이드 알고리즘.

잘 설명된 곳 : http://kks227.blog.me/220796029558

앞의 다익스트라나 벨만 포드는 한 시작점에서 다른 모든 정점까지의 거리를 구한다.

그렇지만 이 플로이드 알고리즘은 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구한다. 

ex) i,j사이의 최단 거리.(i==j일땐 0이다.)