플로이드 워셜 알고리즘1 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) [Python / 파이썬] 1. 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 다익스트라(Dijkstra's) 알고리즘과 같이 최단 경로를 구하는 알고리즘이다. 차이점은 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있고, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라와 다르게 2차원 리스트에 '최단 거리' 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 또한 다익스트라 알고리즘은 그리디 알고리즘인데 플로이드 워셜 알고리즘은 다이나믹 프로그래.. 2022. 1. 16. 이전 1 다음
