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

플로이드 와샬(Floyd Warshall)

모든 정점 에서 모든 정점으로의 최단 경로를 구하고 싶을 때 플로이드 와샬 알고리즘을 사용해야함 , 거처가는 정점(노드)을 기준으로 최단 거리를 구하는 것이 특징이다. 또한 2차원 배열을 사용함.

노드가 자신을 포함한 모든 노드에 대해 비용을 계산하고 점차 값을 비교 하면서 수정을 해나가는 것이 특징이다.

노드	노드1	노드2	노드3	노드4	노드5
노드1	0	3	8	무한	-4
노드2	무한	0	무한	1	7
노드3	무한	4	0	무한	무한
노드4	2	무한	-5	무한	무한
노드5	무한	무한	무한	6	0

0은 자기 자신한테 가는 거라서 0이 되고 , 무한(INF) 은 경로가 없다는 것을 의미함
이제 이 테이블은 현재까지 계산된 최소 비용 테이블이 됨 , 다음은 이차원 배열을 반복적으로 돌아서 값을 갱신해야됨. 거처가는 정점을 기준으로 최단 거리를 찾아서 갱신을 함
노드2 에서 1로 가는 경로의 값과 다른 노드를 거쳐서 가는 값을 서로 비교해서 더 작은 값으로 교체를 함. 무한(INF) VS 2->4->1 = 3 이런식으로 비교해서 노드를 돌면서 값을 바꿈

최단경로

노드	노드1	노드2	노드3	노드4	노드5
노드1	0	1	-3	2	-4
노드2	3	0	-4	1	-1
노드3	7	4	0	5	3
노드4	2	-1	-5	0	-2

이런 식으로 할 수 있다.

핵심 코드

for ( int k = 0 ; k < number ; k++ ) {
	for ( int i = 0 ; i < number ; i++ ) {
    	for ( int j = 0 ; j < number ; j++ ) {
        	if ( ary[i][k] + ary[k][j] < ary[i][j] ) {
            	ary[i][j] = ary[i][k] + ary[k][j];
            }
        }
    }
}

참고 사이트
https://blog.naver.com/ndb796/221234427842
https://ssungkang.tistory.com/entry/Algorithm-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98