[그래프] 플로이드 워셜(Floyd-Warshall Algorithm)

플로이드 워셜(Floyd-Warshall Algorithm)

컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다.

알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.

 

알고리즘

플로이드-워셜 알고리즘은 각각의 꼭짓점 쌍을 지나는 그래프의 모든 경로를 비교한다. 이 방법은 그래프에서 𝛳(|V|³)의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 Ω(|V|²)의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는다.

 

의사코드

출처

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전