[Algorithm] 플로이드-와샬(Floyd-Warshall)

[ 개념 ] 

거쳐가는 정점을 기준으로 최단거리 구하기

 

[ 시간복잡도 ]

O(|n|^3)

[ 흐름 ] 

Dynamic Programming의 일종!

현재까지 계산된 최소비용을 나타내는 정점에대한 테이블이 필요함!

이를 나타낼때 Array[y][x] = y->x로 가는 비용으로 나타냅니다.

 

플로이드와샬은 자기 자신으로 되돌아오는 길이 존재하지않습니다.

그래서

(1) 자기자신으로 되돌아오는 길을 배제할것

(2) 현재위치에서 다른정점을거쳐 현재위치로 올 수 있는 경우와 비교하여 최소값을 가져가면됩니다.

즉, 정점 1, 2, 3이 존재할 때 1->3 의 값과 1->2->3 으로 가는값을 비교하는겁니다

이를 나타내면 Array[1][3] compare Array[1][2] + Array[2][3] 이 됩니다.

 

위 두가지를 신경쓰며 전체적으로 포문을 돌리면됩니다~!

단, (1) 바로가는방법 (2) 정점을 거쳐가는 방법 두가지로 나뉘기때문에 아래 코드처럼 3중포문이 됩니당

 

[ 핵심소스코드 / C++ ] 

void floyd() {
    for (int k = 1; k <= spot; k++)
        for (int y = 1; y <= spot; y++)
            for (int x = 1; x <= spot; x++)
                if (y != x && cost[y][x] > cost[y][k] + cost[k][x])
                    cost[y][x] = cost[y][k] + cost[k][x];
}