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

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

플로이드 워셜 알고리즘이란 모든 정점들간의 상호 최단거리를 구하기 위한 알고리즘이다.

시간복잡도는 O(N^3) 으로 i에서 j를 갈때 i->k->j 와 같이 모든 정점(k)를 거쳐서 i 에서 j를 가면서 가장 가까운 거리를 찾는 알고리즘이다.

기본적인 알고리즘 의사코드는 다음과 같다.

1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
2 for each edge (u,v)
3    dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
4 for each vertex v
5    dist[v][v] ← 0
6 for k from 1 to |V|
7    for i from 1 to |V|
8       for j from 1 to |V|
9          if dist[i][j] > dist[i][k] + dist[k][j]
10             dist[i][j] ← dist[i][k] + dist[k][j]
11         end if

응용 : 네비게이션 시스템,네트웍 커뮤니케이션 등

2. 플로이드워셜(Floyd-Warshall) 알고리즘 예

위와 같은 그래프를 표로 만들면 다음과 같다.

1) k=1 일 때 1부터 4까지 1을 거쳐 가는 모든 경로를 최솟값으로 갱신한다.

2) k=2 일 때 1부터 4까지 2를 거쳐 가는 모든 경로를 최솟값으로 갱신한다.

3) k=3 일 때 1부터 4까지 3를 거쳐 가는 모든 경로를 최솟값으로 갱신한다.

4) k=4 일 때 1부터 4까지 4를 거쳐 가는 모든 경로를 최솟값으로 갱신한다.

이렇게 i~j 경로를 모든 k를 거쳐서 가는 가장 작은 경로를 찾으면 위와 같은 값을 찾을 수 있다. 

 

3. 문제풀이

jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=816&sca=4070

JUNGOL

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int connect[60][60];
int score[60];
 
int main()
{
    //freopen("input.txt","r",stdin);
    int n;
    int a,b;
    int i,j,k;
 
    cin >> n;
 
    for(i=0;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            if(i==j) connect[i][j]=0;
            else connect[i][j]=987654321;
        }
    }
 
 
    while(1)
    {
        cin >> a >> b;
        if(a<0 || b< 0) break;
        connect[a][b]=1;
        connect[b][a]=1;
    }
 
    //플로이드 워셜 알고리즘으로 최단 거리를 찾자.
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(connect[i][j] > connect[i][k] + connect[k][j]) connect[i][j] = connect[i][k] + connect[k][j];
            }
        }
    }
    int minscore = 987654321;
    for(i=1;i<=n;i++) score[i] = 0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++) if(score[i] < connect[i][j]) score[i] = connect[i][j];
        if(minscore > score[i]) minscore = score[i];
    }
 
    int cnt=0;
    for(i=1;i<=n;i++)
    {
        if(minscore == score[i]) cnt++;
    }
 
    printf("%d %d\n",minscore,cnt);
 
    for(i=1;i<=n;i++)
    {
        if(minscore == score[i]) printf("%d ",i);
    }
 
    return 0;
}