플로이드-워셜 썸네일형 리스트형 플로이드-와샬 알고리즘 플로이드-와샬 알고리즘은 그래프에서 최단거리를 구하는 알고리즘 중 하나입니다. 플로이드 알고리즘, 플로이드-워셜 알고리즘 등으로 불리기도 합니다. 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다른 최단거리 알고리즘과 다르게 모든 정점들 사이의 최단거리를 구할 수 있습니다. 정점의 수를 $V$라고 할 때 시간복잡도는 $O(V^3)$으로 꽤 높지만, 상수가 매우 작아 시간복잡도에 비해 빠르며 코드가 간단하다는 장점이 있어 모든 쌍 사이의 최단거리를 구하는 매우 효율적인 알고리즘입니다. 조금 응용하면 최단경로(최단거리인 경로에 속한 정점들) 또한 구할 수 있습니다. 편의를 위해 그래프의 정점의 개수를 $V$라고 부르겠습니다. 또한 이 글을 쉽게 읽으려면 그래프의 정점, 최단거리, 표현 방식 등 기.. 더보기 이전 1 다음
