[알고리즘/자료구조] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 - 워셜 알고리즘은 각각 꼭짓점 쌍을 지나는 그래프의 모든 경로를비교한다. 이 방법은 그래프에서  의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대   의 변이 있을수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때까지 점진적으로 개선시켜서 최단경로를 찾는다.

1에서 ${\displaystyle N}$까지 번호가 매겨진 ${\displaystyle V}$를 꼭짓점으로 갖는 그래프 ${\displaystyle G}$를 생각한다. 그 후 ${\displaystyle i}$에서 ${\displaystyle j}$로 집합 ${\displaystyle \{1,2,\ldots ,k\}}$의 꼭짓점들 만을 경유지로 거쳐 가는 최단 경로를 반환하는 함수 ${\displaystyle \mathrm {shortestPath} (i,j,k)}$를 생각한다. 함수가 주어졌을 때, 목표는 ${\displaystyle \{1,2,\ldots ,N\}}$에 있 꼭짓점만을 이용해서 모든 꼭지점 ${\displaystyle i}$에서 모든 꼭짓점 ${\displaystyle j}$로 가는 최단 경로를 찾는 것이다.

각각의 꼭짓점 쌍에 대해서, ${\displaystyle \mathrm {shortestPath} (i,j,k)}$는 다음 중 한 가지에 속한다:

(1) ${\displaystyle k}$를 통과하지 않는 경로 (집합 ${\displaystyle \{1,\ldots ,k-1\}}$에 있는 꼭짓점만 거쳐간다.)

(2) ${\displaystyle k}$를 통과 하는 경로 (${\displaystyle i}$에서 ${\displaystyle k}$까지와 ${\displaystyle k}$에서 ${\displaystyle j}$까지 가는 경로 모두 ${\displaystyle \{1,\ldots ,k-1\}}$에 있는 꼭짓점 만을 거쳐간다)

${\displaystyle i}$에서 ${\displaystyle j}$까지 ${\displaystyle 1}$에서 ${\displaystyle k-1}$의 꼭짓점 만을 거쳐가는 경로 중 최선의 경로는 ${\displaystyle \mathrm {shortestPath} (i,j,k-1)}$에 의해 정의된다는 것은 알고 있으며, 만약 ${\displaystyle i}$에서 ${\displaystyle k}$를 거쳐 ${\displaystyle j}$로 가는 더 나은 경로가 있다면, 그 경로는 ${\displaystyle i}$에서 ${\displaystyle k}$까지 (${\displaystyle \{1,\ldots ,k-1\}}$만을 거쳐서) 가는 경로와 ${\displaystyle k}$에서 ${\displaystyle j}$까지 (${\displaystyle \{1,\ldots ,k-1\}}$만을 거쳐서) 가는 경로를 합친 것이라는 것은 자명하다.

${\displaystyle w(i,j)}$이 꼭짓점 ${\displaystyle i}$와 ${\displaystyle j}$ 간의 변의 가중치라면, ${\displaystyle \mathrm {shortestPath} (i,j,k)}$를 다음의 재귀적 공식으로 정의할 수 있다: 기본적인 경우는

${\displaystyle \mathrm {shortestPath} (i,j,0)=w(i,j)}$

이고 재귀적인 경우는 다음과 같다

${\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {\Big (}\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm {shortestPath} (i,k,k-1)+\mathrm {shortestPath} (k,j,k-1){\Big )}}$.

이 공식은 플로이드-워셜 알고리즘의 핵심이다. 이 알고리즘은 처음에 모든 ${\displaystyle (i,j)}$쌍에 대해서 ${\displaystyle k=1}$일 때 ${\displaystyle \mathrm {shortestPath} (i,j,k)}$를 계산하고, 다음으로 ${\displaystyle k=2}$일 때를 계산하는 식으로 ${\displaystyle k=N}$이 될 때까지 계속하면, 모든 ${\displaystyle (i,j)}$쌍에 대해서 최단 경로를 찾게 된다.

소스

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 12 - 12
/*
*/
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
 
#define INF 1048576
 
using namespace std;
 
void main()
{
    int arr[6][6];
    for(int i = 0; i < 6; i++)
    {
        for(int j = 0; j< 6; j++)
        {
            if( i == j)
            {
                arr[i][j] = 0;
            }
            else
            {
                int random = ( rand() % 10) + 1;
                arr[i][j] = random;
            }
        }
    }
 
    arr[0][4] = INF;
    arr[3][1] = INF;
    arr[2][5] = INF;
    arr[6][1] = INF;
    arr[5][3] = INF;
    arr[3][4] = INF;
    arr[0][1] = INF;
 
    for(int i = 0; i < 6; i++)
    {
 
        for(int j = 0; j < 6; j++)
        {
            for(int k = 0; k< 6; k++)
            {
                if(arr[j][k] == INF)
                {
                    cout << "INF\t";
                }
                else
                {
                    cout << arr[j][k] << "\t";
                }
            }
            cout << endl;
        }
        
        cout << endl;
        cout << endl;
 
        for(int j = 0; j < 6; j++)
        {
            for(int k = 0; k < 6; k++)
            {
                if( arr[j][k] > arr[j][i] + arr[i][k])
                    arr[j][k] = arr[j][i] + arr[i][k];
            }
        }
    }
 
    for(int i = 0; i < 6; i++)
    {
        for(int j = 0; j< 6; j++)
        {
            if(arr[i][j] == INF)
            {
                cout << "INF\t";
            }
            else
            {
                cout << arr[i][j] << "\t";
            }
        }
        cout << endl;
    }
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm