플로이드 워셜(Floyd-Warshall)
지금까지 다룬 다익스트라나 벨만-포드 알고리즘들은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구해 주었다. 하지만 한 개의 시작점이 아니라 모든 정점 쌍에 둘 사이의 최단 거리를 구해야 할 때도 있다. 이러한 문제를 해결하는 가장 쉬운 방법은 모든 정점으로부터 다익스트라 알고리즘을 적용하면 되는 것이다. 만약 음수 가중치가 있다면 벨만 포드 알고리즘을 사용하면 된다. 그러나 이것보다 좀 더 빠르고 간단한 방법이 있다. 그것은 이제 설명할 플로이드 워셜(Floyd-Warshall) 알고리즘이다. 플로이드 워셜 알고리즘은 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][]를 계산한다. 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 우선..
알고리즘/이론
2023. 6. 28. 23:09
