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

1. 개념

정점 V개가 있고, 거리가 모두 주어져 있을 때 단 한 번의 시행으로 모든 정점 쌍 사이의 거리를 모두 구하는 알고리즘이다.

음의 가중치가 있는 간선 그래프에서도 사용이 가능한 것이 특징이다.

2. 구현

플로이드 알고리즘은 전형적인 3중 for문의 형태를 하고 있고, 시간 복잡도가 O(n^3)이다.

각 정점 a, b 쌍에 대해서 a에서 b로 가는 최단 경로를 한 번에 다 구해야하므로 2차원 배열 ary를 준비한다.

초기값은 자기 자신에게 가는 ary[i][i] = 0 , 나머지는 ary[i][j] = ∞ 로 초기화한다.

그리고 간선 정보를 받은 후에 a->b로 가는 거리가 w라면 ary[a][b] = w로 갱신한다.

만약 a->b로 가는 거리가 여러 개라면 그 중 가장 작은 값을 사용한다.

플로이드는 최단경로를 DP 형태의 문제로 정의하고 해결한다.

shortestPath(i,j,k)는 i번 정점에서 j번 정점까지 1~k번 정점만을 사용할 때의 최단 거리를 구하라는 의미이다.

k단계 문제를 해결하기 위해서는 k-1단계의 정보가 필요하므로 k=1~N까지 시도하며 정보를 계속해서 갱신한다.

이때, k-1단계 이전의 정보는 더이상 필요하지 않기에 3차원 배열을 쓰지 않고 슬라이딩 윈도우 기법을 적용해 덮어써

2차원 배열 ary만으로도 해결할 수 있다.

매 단계에서 하는 일은 다음과 같다.

k단계, 즉 1~k번 정점을 사용해 도달가능한 최단거리를 구해야 하는 단계라고 하자.

그렇다면 지금까지 ary배열에는 1~k-1번 정점만 사용해서 나올 수 있는 최단거리가 남아있다.

우리는 이걸 사용해서 갱신해야한다.

어떤 두 정점 i,j에 대해 k번 정점을 사용해 우회하면 지금까지보다 최단거리가 짧아지는지에 대해 알아보고,

더 짧다면 갱신해야 한다. 이 조건문의 형태는

if(dist[i][j] > dist[i][k] + dist[k][j])

형태가 된다. 

*참고 블로그 : https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220797649276&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F

[플로이드 예제 : http://gyutts.tistory.com/66]