최단 경로1 [2] Floyd-Warshall 알고리즘 플로이드 워셜 알고리즘은 그래프에서 "All-pair-shortest-path" - 정점들의 모든 쌍의 최단 경로의 길이를 구하는 알고리즘이다. 그래프 알고리즘 중 가장 단순한 알고리즘이라고 생각된다. Brute-Force랑 거의 같다고 볼 수 있기 때문이다. 알고리즘도 단순하다. pseudo-code를 보자. 다음과 같이 Floyd-Warshall은 for문 3개로 돌아간다. 의미를 해석하자면 i에서 j로 가는 길의 거리를 생각했을 때, i에서 j로 바로 가는게 빠른지 -> (d_ij) 아니면 k를 경유하여 가는게 빠른지를 비교해서 (d_ik + d_kj) 더 작은 길의 값이 지정이 되는 것이다. (min) 저장되는 그래프 D의 dij는 곧 i에서 j로 가는 최단 거리가 지정이 될 것이다. 2020. 4. 12. 이전 1 다음
