플로이드-와셜 알고리즘

플로이드-와셜 알고리즘(Floyd-Warshall Algorithm})은 그래프에서 모든 정점간의 최단거리를 구하는 알고리즘이다. 음수 간선도 사이클만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 정점이고, 두 번째 반복문은 출발하는 정점, 세 번째 반복문은 도착하는 정점이다. 이 알고리즘은 플로이드 알고리즘이랑은 다르다.

소스 코드

C 언어

void _back(int i, int j){
        if(!b[i][j]){
                printf("%d ", i);
                return;
        }
        _back(a, b[i][j]);
        _back(b[i][j], b);
}
 
void back(int i, int j){
        _back(i,j);
        printf("%d\n", j);
}
void floyd(){
        for(int i = 1; i <= N; i++){
                for(int j = 1; j <= N; j++){
                        d[i][j] = w[i][j]; //k=0
                }
        }
        for(int k = 1; k <= N; k++){
                for(int i = 1; i <= N; i++){
                        for(int j = 1; j <= N; j++){
                                if(d[i][j] > d[i][k] + d[k][j]){
                                        d[i][j] = d[i][k] + d[k][j];
                                        b[i][j] = k;
                                }
                        }
                }
        }
}