모든 정점에서 정점
-
Floyd Wharshall 플로이드 와샬Algorithm/Theory 2020. 6. 18. 13:24
목표 - 하나의 정점에서가 아닌 모든 정점에서 모든 정점으로 가는 최단 경로를 구하고 싶을 때 사용한다. - 거쳐가는 정점을 기준으로 알고리즘을 수행한다. - 삼중 for문을 사용해 구현하므로 O(n^3)의 시간 복잡도를 갖는다. 플로이드 와샬 알고리즘 ? 플로이드 와샬 알고리즘은 한 정점에서 시작해 모든 정점을 탐색하는 최단 방법을 다룬 다익스트라나 다른 그래프 탐색 알고리즘과 달리 모든 정점에서 모든 정점의 최단 경로를 구하고 싶을 때 사용합니다. 핵심 아이디어는 A -> B 노드로 갈 때, A -> B 로 바로 가는 경우 와 A -> K -> B 로 어떤 노드 k를 거쳐가는 방법 을 비교해서 최소값을 구하자는 것입니다. 구현은 가중치 테이블을 이용합니다. 아직 연결이 되지 않은 노드는 ∞으로 두고 ..