플로이드 와샬 알고리즘(Floyd Warshall)

플로이드 와샬 알고리즘

모든 정점에서 모든 정점으로의 최단 경로

다이나믹 프로그래밍 사용

 

시간복잡도 O(N^3)

+) 다익스트라 알고리즘과 달리 음의 간선도 사용 가능

 

탐색

 

1) 시작

연결되지 않은 것은 아직 최소값을 모르니 무한대로 둔다

이제 각 정점을 중간 경유지로 사용할 경우를 살펴보며 경로를 갱신한다.

 

2) 1을 경유지로 정했을 때

정점2에 정점1을 경유해서 다른 정점으로갈 경우를 살펴보자

2-1

2-2

2-3 → 2-1-3 = 무한대, 무한대 같으므로 일단 유지

2-4 → 2-1-4 = 3이 무한대 보다 작으므로 3 유지

2-5 → 2-1-5 = 6이 무한대 보자 작으므로 6 유지

 

정점3에 정점1을 경유해서 다른 정점으로갈 경우를 살펴보자

3-1

3-2 → 3-1-2 = 3이 무한대 보다 작으므로 3 유지

3-3

3-4 → 3-1-4 = 무한대, 무한대 같으므로 일단 유지

3-5 → 3-1-5 = 무한대, 무한대 같으므로 일단 유지

 

정점4에 정점1을 경유해서 다른 정점으로갈 경우를 살펴보자

4-1

4-2 → 4-1-2 = 무한대 보다 -1+2이 작으므로 1 기입 (변경사항)

4-3 → 4-1-3 = -4이 -1+7이 작으므로 -4 유지

4-4

4-5 → 4-1-5 = 무한대 보다 -1+4가 작으므로 3 기입 (변경사항)

 

정점5에 정점1을 경유해서 다른 정점으로갈 경우를 살펴보자

5-1

5-2 → 5-1-2 = 무한대, 무한대 같으므로 일단 유지

5-3 → 5-1-3 = 무한대, 무한대 같으므로 일단 유지

5-4 → 5-1-4 = 5가 무한대 보다 작으므로 5 유지

5-5

 

2) 2~5를 경유지로 정했을 때

위의 상황을 반복한다

 

3) 최종 표

정점에서 각 모든 정점을 방문하는 최소 값을 구할 수 있다

 

점화식

D[i][j]=min(D[i][j],D[i][k]+D[k][j])

D[i][j] = i-j로 바로 이동하는 경우와

D[i][k]+D[k][j]  = i에서 경유지 k를 거친 후 j로 이동하는 경우

이 둘 중 더 짧은 것으로 갱신해 준다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 2000000
using namespace std;

int main() 
{
    // set graph//////////////////////////////////////////////////////
    int n = 5;
    vector<vector<int>> graph(n, vector<int>(n, INF));
    graph = 
    {
        {0,2,7,INF,4 },
        {INF, 0, INF, 3,6},
        {INF,3,0,INF,INF},
        {-1,INF,-4,0,INF},
        {INF,INF,INF,5,0}
    };


    // 플로이드 와샬 알고리즘//////////////////////////////////////////
    for (int k = 0; k < n; k++) { // 경유지
        for (int i = 0; i < n; i++) { // 출발지
            for (int j = 0; j < n; j++) { // 도착지
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }

    return 0;
}

 

+) 결과 출력 코드

 for (int i = 0; i < n; i++) 
 {
     for (int j = 0; j < n; j++) 
     {
         if (graph[i][j] == INF) { cout << "X";  }
         else { cout << graph[i][j] << " "; }
     }
     cout << "\n";
 }

출력해보면 잘 나온다.