Floyd's Algorithm [플로이드 알고리즘]

플로이드 알고리즘은 모든 정점끼리의 최단경로를 구하는 문제입니다.

void floyd(int n, int S[][N], int P[][N]){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            P[i][j]=0;
        }
    }
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(S[i][j]>S[i][k]+S[k][j] && S[i][k]!=INF && S[k][j]!=INF){
                    S[i][j] = S[i][k]+S[k][j];
                    P[i][j] = k;
                }
            }
        }
    }
}

void path(int i, int j, int P[][N]){
    if(P[i][j]!=0){
        path(i,P[i][j],P);
        cout<<P[i][j]<<' ';
        path(P[i][j],j,P);
    }
}

정점끼리의 관계는 n*n 배열로 나타내며, INF는 현재 갈 수 없는 곳을 나타냅니다.

i와 j는 각각 출발점과 도착점이고, k는 경유지입니다.

따라서 S[i][j] > S[i][k] + S[k][j]를 만족한다면 i에서 j로 바로 가는 것보다 i에서 k를 들렸다가 j를 가는게 더 가까운 게 되는거죠.

 

P[i][j]는 i에서 j로 갈 때 들린 경로 k를 저장합니다. 

정점 1:10이 있고, i=1, j=10이라고 합시다.

만약 P[i][j] = 3이라면 i에서 j로 갈 때 3번 정점을 들렸다는 뜻입니다.

여기서 끝나면 안되고, i에서 3번 정점을 갈 때, 3번 정점에서 j로 갈 때도 어디를 들렸는지 구해야 합니다.

 

따라서 위 path 함수는 i에서 j를 가는동안 들린 경유지를 순서대로 출력합니다.

 

시간 복잡도는 𝜃(n*n*n)=𝜃(n³)으로 항상 일정합니다.