Floyd-Warshall Algorithm과 running time

정의

• 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘
• 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 
• 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다.

running time

• 플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 O(V^3)의 시간 복잡도를 갖는다. 
• 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 O(V)의 시간 복잡도를 갖는다.
•  종종 데이크스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.

소스코드 :https://github.com/JaeguKim/Algorithm/tree/master/Floyd
추가 참고 :http://hsp1116.tistory.com/45