알고리즘 - 모든 쌍 최단 경로 문제(All Pairs Shortest Paths)

각 쌍의 점 사이의 최단 경로를 찾는 문제

 

다익스트라의 최단 경로 알고리즘

- 한 정점에서 모든 정점으로의 최단경로를 구함

- 각 점을 시작점으로 정하여 다익스트라 알고리즘 수행

- 시간 복잡도는 O(n^3)

- 가장 적은 비용의 정점을 기준으로 하나씩 선택해 가며  구해냄.

 

플로이드-워샬(Floyd_Warshall) 알고리즘

- 모든 정점에서 모든 정점으로의 최단 경로를 구함.

- 거쳐가는 정점을 기준으로 알고리즘 수행