플로이드 워셜 (1) 썸네일형 리스트형 플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드-워셜 (Floyd-Warshall) 플로이드-워셜 (이하 플로이드)알고리즘은 그래프에서 최단거리를 찾을 때 사용하는 알고리즘이다. 그래프에서의 최단거리를 찾을 때 가장 대표적인 알고리즘은 다익스트라(링크) 알고리즘이다. 다익스트라 알고리즘은 특정 시작지점에서 모든 노드까지의 최소거리를 알고 싶을 때 사용했다. 즉 다익스트라를 이용하면 하나의 시작노드에서의 정보밖에 얻을 수 없다. 그렇다면 모든 노드를 시작지점으로 해서 각 노드까지의 최소거리를 모두 알고 싶다면 어떻게 할까? 가장 먼저 떠오르는 생각은 다익스트라 알고리즘을 V(정점의 개수)만큼 반복시키는 것이다. 다익스트라 알고리즘 설명에서 다익스트라의 시간복잡도는 O(E*logV)라고 했다. 이는 우선순위 큐를 바이너리 힙으로 구현했을 때의 이.. 이전 1 다음
