Floyd-Warshall Algorithm

[알고리즘] Floyd-Warshall 

이 알고리즘은 Transitive closure나 다대다 최단 거리를 구할 때 사용하는 알고리즘이다. 동적계획법(Dynamic Programming) 기법이 포함되어 있다. 

Transitive closure란 간접적으로 연결되어 있는 간선을 직접갈 수 있는 간선을 추가한 그래프이다.

즉, 이 그래프는 원하는 정점이 서로 직접 혹은 간접적으로 연결되어 있냐를 확인할 수 있다.

pseudo code는 아래와 같다. 

D: 주어진 인접행렬 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| D[i][j] := D[i][j] | (D[i][k] & D[k][j]) return D

D[i][j] := D[i][j] | (D[i][k] & D[k][j]) 

이 부분의 의미는 원래 연결되어 있거나 정점 k를 통해 지나갈 수 있으면 D[i][j]를 갱신하는 부분이다.

만약에 원래 연결되어 있지 않고, k를 통해 갈 수도 없다면 false 값이 들어갈 것이다.

위를 이용해서 최단거리 또한 구할 수 있다. pseudo code는 아래와 같다.

D: 최단거리를 저장할 그래프. 모든 값을 무한대(혹은 최댓값)로 설정해 놓는다. W: 각 간선의 가중치 M: 경로를 기억할 그래프. 모든 성분을 null로 초기화 for i from 1 to |V| D[i][i] := 0 //자기 자신으로 가는 것 0 for j from 1 to |V| D[i][j] := W[i][j] for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if D[i][j] > D[i][k] + D[k][j] D[i][j] = D[i][k] + D[k][j] M[i][j] = k return D

초기 그래프에 모든 값을 무한대로 설정해두고, 최솟값이 발생하면 최솟값으로 갱신시키는 알고리즘이다.

첫번째 정점을 통해 갈 수 있는 모든 최단 거리를 계산한 뒤, 두번째 정점을 통해, 세번째 정점을 통해

이런식으로 점점 정점을 개방하여 최단 거리를 계산한다. 

M과 같은 경우 최단 거리를 갱신하기 위해 마지막으로 경유한 경유지도 기록할 수 있다. 

이렇게 Floyd-Warshall은 삼중포문으로 이루어져 있다. 시간 복잡도도 O(n³)이다. 

그리고 이 알고리즘은 DFS를 모든 정점을 시작점으로 돌림으로써 똑같은 결과를 얻을 수 있는데, 경우에 따라 속도가 다르기 때문에 누가 더 빠르다고 말할 수 없다. 만약 주어진 간섭이 많은 경우에는 Floyd-Warshall이 더 빠른 것으로 알려져 있다. 

참고: https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98