Floyd-Warshall (1) 썸네일형 리스트형 117. Floyd-Warshall 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로, 그래프의 정점의 수가 $n$일 때 시간복잡도는 $\Theta(n^3)$이다. 플로이드-와샬 알고리즘은 정점들 사이의 최단 거리를 구할 때 중간에 거칠 수 있는 정점의 수를 늘려 나가면서 최단 거리를 갱신하는 방식으로 작동한다. 벨만-포드 알고리즘이 간선을 확인하는 것과는 약간 다르다. 구체적인 작동 방식은 다음과 같다. 1. 정점 $i$로부터 정점 $j$까지의 최단 거리를 $d_{i, j}$라고 한다. 2. 각각의 $d_{i, j}$에 대해 $i = j$인 경우 $d_{i, j} = 0$, $i \ne j$인 경우 $d_{i, j} = \infty$로 초기화한다. 3. .. 이전 1 다음
