[알고리즘] Floyd I vs Floyd II - 최단거리 계산 알고리즘

Floyd 알고리즘 I

• 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리 를 계산하라.
• 입력: 가중치 포함, 방향성 그래프 와 그 그래프에서의 정점의 수 .
• 출력: 최단거리의 길이가 포함된 배열
• 알고리즘

void floyd(int n, const number W[][], number D[][]) {
    int i, j, k;
    D = W;
    for(k=1; k <= n; k++)
        for(i=1;  i <= n; i++)
            for(j=1; j <= n; j++)
            D[i][j] = minimum(D[i][j],D[i][k]+D[k][j]);
}

• 모든 경우를 고려한 분석:
  • 단위연산: for-j 루프안의 지정문
  • 입력크기: 그래프에서의 정점의 수
  • 

Floyd 알고리즘 II

• 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계 산하고, 각각의 최단경로를 구하라.
• 입력: 가중치 포함 방향성 그래프 와 그 그래프에서의 정점의 수 .
• 출력: 최단경로의 길이가 포함된 배열 , 그리고 다음을 만족하는 배열 P.

• 알고리즘

void floyd2(int n, const number W[][], number D[][], index P[][]) {
    index i, j, k;
    for(i=1; i <= n; i++)
        for(j=1; j <= n; j++)
            P[i][j] = 0;
    D = W;
    for(k=1; k<= n; k++)
        for(i=1; i <= n; i++)
            for(j=1; j<=n; j++)
                if (D[i][k] + D[k][j] < D[i][j]) {
                    P[i][j] = k; // 최솟값 저장
                    D[i][j] = D[i][k] + D[k][j];
                }
}