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

Floyd-Warshall 알고리즘이란 ?

Floyd-Warshall 알고리즘이란, 변의 가중치가 음이거나 양인 ( 음수 사이클은 없는 ) 가중 그래프에서 모든 최단 경로를 구하는 방법 이다.

다익스트라와 벨만포드 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 방법 이다.

Dijkstra 알고리즘

• 정해진 출발지 vertex 에서 부터 다른 모든 vertex으로의 최단 경로를 구한다.
• 가장 작은 가중치를 하나씩 선택해나간다. ( 우선순위 큐 이용 )

Floyd-Warshall 알고리즘

• 모든 vertex 에서 모든 vertex 로의 최단 경로를 한번에 구한다. 즉, 모든 vertex 쌍의 최단 경로를 구한다.
  • 모든 쌍을 표현하는 이차원 배열 을 선언하고, Dynamic Programming 방식으로 각 쌍의 최단거리를 업데이트한다.

진행 과정

• i행과 j열의 원소인 (i, j) 원소는 vertex i로부터 vertex j까지의 최단 경로이다.
• 점화식 👉 dist[i, j] = min(dist[i, j], dist[i,k] + dist[k,j])
  • vertex i에서 vertex k를 거쳐서 vertex j로 갈 때, i에서 바로 j로 가는 것보다 짧다면 업데이트

시간 복잡도

vertex의 갯수 V 만큼 반복문이 3중으로 수행되고 있기 때문에 O(V3)의 시간 복잡도를 갖는다.
그리고 간선들의 정보를 V * V 크기의 행렬에 저장했기 때문에 O(V2)의 공간 복잡도를 갖는다.