최단 경로를 구하는 문제 유형은 크게 분류하면 아래와 같습니다.

1. 하나의 정점에서 출발하였을 때 하나의 정점까지 최단 경로를 구하는 유형

2. 하나의 정점에서 모든 정점까지의 최단 경로를 구하는 문제 - 다익스트라, 벨만-포드

3. 특정 정점으로 가는 모든 최단 경로를 구하는 유형

4. 모든 정점에서 모든 정점으로의 최단 경로를 구하는 유형 - 플로이드-워셜

플로이드 - 워셜 알고리즘

[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

다익스트라 알고리즘과 유사하게, 플로이드-워셜 알고리즘 또한 아래 점화식을 토대로 DP 방식을 따른다.

→ 모든 노드를 순회하면서, 해당 노드를 거쳐서 가는 방법과 거치지 않고 가는 방법 중 더 적은 비용이 드는 값으로 갱신하는 것이다. (= 이는 다익스트라와 동일)

다익스트라에서는 다음에 방문할 노드를 선택할 때, 아직 방문하지 않은 노드 중에서 시작점으로부터 가장 가까운 노드를 선택(= 그리디)했다면, 플로이드-워셜 알고리즘은 이 과정을 필요로 하지 않는다.

또한, 플로이드-워셜은 모든 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘이기 때문에, 2차원 배열에 값을 저장한다. (행: 시작 노드, 열: 종점 노드)

다만 플로이드-워셜 알고리즘의 경우에는 O(N^3)이라는 다소 높은 시간 복잡도를 갖고 있어서 자주 활용하기에는 어려움이 있지 않을까 생각한다.

플로이드 워셜 알고리즘은 앞서 다룬 최단경로 알고리즘보다 훨씬 단순하기 때문에, 위에 링크를 걸어둔 포스팅을 한번 정독하면 바로 이해할 수 있을 것이다.