플로이드-와셜 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

소스 코드[편집]

C 언어[편집]

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;
                }
            }
        }
    }
}