참고
플로이드-워셜(Floyd-Warshall)
NOTE
모든 최단 경로를 구하는 알고리즘
•
다익스트라가 모든 정점까지의 최단거리를 구한다면
•
플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드간 최단 경로를 구할 수 있다.
•
기본적으로 DP기술에 의거한다.
•
음수 사이클만 존재하지 않는다면 가중치가 음수여도 상관없다
※ 음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아 왔을때, 최종적인 비용이 음수가 되는 경우.
플로이드 워셜 - 원리
NOTE
•
모든 정점을 Middle로 둔 경우들에 대해 갱신한다
dist[From][To] = min(dist[From][To], dist[From][Middle] + dist[Middle][From])
플로이드 워셜 - 수행과정
NOTE
•
모든 노드간 최단거리를 구해야하므로 2차원 인접행렬을 구성한다
1.
1번 노드를 새로운 중간노드로 설정
•
이 그래프는 1~5번 노드까지 존재하므로 5단계가 진행된다
•
2 → 4의 경우 원래는 길이 없으나 2 → 1 → 4로 갈 수 있게됨
2.
2번 노드를 새로운 중간 노드로 설정
3.
이런식으로 3~5번 노드를 중간 노드로 계속해서 거쳐가면서 최단 거리를 구한다
플로이드 워셜 - 소스코드 구현
NOTE
•
플로이드-워셜 알고리즘은 시간 복잡도가 O(n^3)으로, 그래프의 크기가 작은경우에만 사용하는게 좋다