최단 경로 알고리즘 - Floyd Warshall

Floyd Warshall

• 모든 정점 쌍 사이의 최단 거리
• 음의 간선 가중치 가능
• 인접 행렬 사용하여 삼중 for문
• O(V^3)

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