플로이드 워셜 알고리즘

1 개요

Floyd-Warshall Algorithm

플로이드-워셜 알고리즘

• 그래프에서 모든 정점 사이의 최단 경로를 찾는 알고리즘
• 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘
• 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다.
• 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다.
• 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다.
• 활용 예시: 운송 회사는 플로이드-워셜 알고리즘을 사용하여 배송 경로를 최적화할 수 있다.
• 시간 복잡도: [math]\displaystyle{ O(V^3) }[/math] (V는 그래프의 정점 수)
• 1962년 로버트 플로이드와 스티븐 워셜이 발표했다.
• 플로이드는 공로를 인정받아 튜링상을 받았다.

2 절차

• 모든 정점 사이의 거리를 무한대로 초기화한다.
• 각 정점을 거쳐 모든 정점 사이의 거리를 갱신한다.
• 모든 정점 사이의 최단 경로를 찾는다.

3 같이 보기

• 데이크스트라 알고리즘
• 벨먼 포드 알고리즘

4 참고

• 위키백과 "플로이드 워셜 알고리즘"
• 다음백과 "플로이드 워셜 알고리즘"
• 네이버백과 "플로이드 워셜 알고리즘"
• 나무위키 "플로이드 워셜 알고리즘"
• 리브레 위키 "플로이드 워셜 알고리즘"