자료구조 :: 그래프(7) Floyd의 최단 경로 알고리즘

# Floyd의 최단경로 알고리즘

Floyd의 최단경로 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘
이다. Floyd의 최단 경로 알고리즘은 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성되어 있다. 알고리즘
자체는 매우 간단하다.

Floyd 알고리즘

(1) 정점 k를 거쳐서 가지 않는 경우
정점 i에서 j로 가는 경우 최단 거리는 당연히 A[i][j]가 된다.

(2) 정점 k를 거쳐서 가는 경우
이 경우 i에서 k까지 최단거리 A[i][k]에다가 k에서 j까지 최단거리인 A[k][j]를 더한 값이 될 것이다.

따라서 최종적인 최단거리는 당연히 (1)과 (2)중에서 더 적은 값이 될 것이다.

if (A[i][k]+A[k][j] < A[i][j]) 
       A[i][j] = A[i][k]+A[k][j];

위 코드처럼 표현이 가능하다. 이는 정점 k를 경우하는 것이 보다 좋은 경로이면 A[i][j]값이 변경되고 그렇지
않으면 이전 값을 유지한다는 의미이다.

두개의 정점 사이의 최단 경로를 찾는 Dijkstra의 알고리즘은 시간 복잡도 O(n²)이므로, 모든 정점쌍의 최단경로를
구하려면 Dijkstra의 알고리즘을 n번 반복해야 하고, 따라서 전체 복잡도는 O(n³)이 된다. 한번에 모든 정점 간의
최단 경로를 구하는 Floyd의 알고리즘은 3중 반복문이 실행되므로 시간 복잡도가 O(n³)으로 표현되고, 이는
Dijkstra의 알고리즘과 비교해 차이는 없다고 할 수 있다. 그러나 Floyd의 알고리즘은 매우 간결한 반복구문을
사용하므로 Dijkstra의 알고리즘 보다 상당히 빨리 모든 정점간의 최단 경로를 찾을 수 있다.

Intoroduction to Algorithms(2nd)의 Floyd 알고리즘 부분이다.

Time : O(n³), but simpler operations then FLOYD-WARSHALL, 참 매력적인 말이다.

floyd.cpp

#include <stdio.h> 
#include <limits.h> 

#defineTRUE1
#defineFALSE0
#define VERTICES    7/* 정점의 수 */
#define INF    10000/* 무한대 (연결이 없는 경우) */

/* 네트워크의 인접행렬 */
int weight[VERTICES][VERTICES]={ 
    {   0,  7,  INF, INF,   3,  10, INF }, 
    {   7,  0,    4,  10,   2,   6, INF }, 
    { INF,  4,    0,   2, INF, INF, INF }, 
    { INF, 10,    2,   0,  11,   9,   4 }, 
    {   3,  2,  INF,  11,   0, INF,   5 }, 
    {  10,  6,  INF,   9, INF,   0, INF }, 
    { INF, INF, INF,   4,   5, INF,   0 }}; 

int A[VERTICES][VERTICES]; 

printA(int n) 
{ 
int i, j, k; 
    printf("===============================\n"); 
for(i=0; i<n; i++){ 
for(j=0; j<n; j++){ 
if( A[i][j] == INF ) 
                printf("INF "); 
else printf("%3d ", A[i][j]); 
        } 
        printf("\n"); 
    } 
    printf("===============================\n"); 
} 
void floyd(int n)   
{  

int i, j, k; 
for(i=0; i<n; i++) 
for(j=0; j<n; j++) 
            A[i][j]=weight[i][j]; 

for(k=0; k<n; k++){ 
for(i=0; i<n; i++) 
for(j=0; j<n; j++) 
if (A[i][k]+A[k][j] < A[i][j]) 
                     A[i][j] = A[i][k]+A[k][j]; 
                printA(n); 
        } 
} 

main() 
{ 
    floyd(VERTICES); 
}