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

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하 세요.

#. Solve

다익스트라, 벨만-포트 알고리즘은 그래프의 한 정점에서 다른 정점으로 가는 최단 거리를 구하는 알고리즘이라면,

플로이드-워셜은 그래프의 모든 정점에서 모든 정점으로 가는 최단거리, 그 최소 비용을 구하는 알고리즘이다.

모든 정점에서 모든 정점을 방문해야하므로 그래프는 2차원 배열로 구성

입력이 아래와 같을 때,

5 8

1 2 6

1 3 3

3 2 2 

2 4 1 

2 5 13 

3 4 5 

4 2 3 

4 5 7

dis[i][j]를 i 정점에서 j 정점으로 가는 최소 비용이라고 해보자.

이동할 수 없을 때는 비용을 'M'으로 한다고 했으니,

dis[][]는 'M'을 초기값으로 초기화한다.

//

자기자신으로 가는 비용은 0이고 

입력으로 주어진 인접행렬 정보를 dis[][]에 저장한다.

//

여기서부터가 중요하다.

i정점부터 j정점까지 이동하는 최소 비용을 구할건데,

i ~ j 사이에 1~n까지의 정점을 모두 넣어보는 것이다.

K = 1,

먼저 1을 i~j까지의 거리에 모두 넣어보고, 기존보다 최소 비용이 나올 경우 수정해주면 된다.

min(dis[i][j], dis[i][k]+dis[k][j])

결과는 그대로다... i부터 j까지 1을 거쳐서 갔을 때, 더 적은 비용으로 가는 경우가 없었다 보다

  

먼저 k = 1 && i == 1일 경우, 결과는 동일하다.

1->1->1은 (1->1)과 같고, 1->1->2은 (1->2)와 같고, 1->1->3은 (1->3)과 같으므로 결국 원점...

k = 1 && i = 2일 때,  

2->1->1 = 갈 수 없음, M

2->1->2 = 2에서 1로 갈 수 없으므로 결과는 M+6이 되어 최소인 0을 저장

2->1->3 = 마찬가지로 2에서 1로 갈 수 없으므로 결과는 M+3이 되어 최소인 M을 저장

2->1->4 = 1, 2에서 1을 갈 수 없고, 1에서 4로도 갈 수 없어서 결과는 M+M이 되어 최소인 1을 저장

...

k = 1 && i = 3일 때, 

3->1->1 = 갈 수 없음, M

3->1->2 = 3에서 1을 갈 수 없으므로 결과는 M+6이 되어 최소인 2를 저장

3->1->3 = 마찬가지로 3에서 1을 갈 수 없으므로 결과는 M+3이 되어 최소인 0을 저장

3->1->4 = 3에서 1을 갈 수 없으므로 결과는 M+M으로 최소인 5를 저장

...

...

//

K = 2 (i에서 j까지 이동하는데 2를 거쳐 갈 경우)

min(dis[i][j], dis[i][k]+dis[k][j]) 적용

기존과 수정된 부분만 살펴보면

K = 2, i = 1

1->2->1 = min(0, 6 + M) = 0

1->2->2 = min(6, 6) = 6

1->2->3 = min(3, 6+M) = 3

1->2->4 = min(M, 6+1) = 7

1->2->5 = min(M, 6+13) = 19

...

//

K = 3 (i에서 j까지 이동하는데 3을 거쳐 갈 경우)

min(dis[i][j], dis[i][k]+dis[k][j]) 적용

기존과 수정된 부분만 살펴보면

K = 3, i = 1

1->3->1 = min(0, 3 + M) = 0

1->3->2 = min(6, 3+2) = 5

1->3->3 = min(3, 3) = 3

1->3->2->4 = min(7, 3+2+1) = 6 

(이미 1->2->4로 2를 거쳐갔을 경우 최소 비용을 가진 상태에서 3을 중간에 더 거친 상황이다)

1->3->2->5 = min(19, 3+2+13) = 18

(이미 1->2->5로 2를 거쳐갔을 경우 최소 비용을 가진 상태에서 3을 중간에 더 거친 상황이다)

* 여기서 보면 중간에 정점을 거치는 순서가 순열 순서로 적용될 수 있다는 것을 알 수 있다.

   비용이 제일 작은 순으로 테이블에 저장하게 된다.

...

//

계속 동작시켜보면 아래와 같은 결과를 얻을 수 있다.

K = 4 (i에서 j까지 이동하는데 4을 거쳐 갈 경우)

K = 5 (i에서 j까지 이동하는데 5을 거쳐 갈 경우)

여기서 중요한 것은

모든 정점이 순서대로 방문하는 것이 아니라 순열 순서로 적용될 수 있다는 점이다.

위 과정에서도 보았듯이 1->2->3->4 순서 뿐 아니라 1->3->2->4 순서로도 정점을 방문할 수 있다.

2를 거쳐서 갔을 때 최소 비용이였는데, 중간에 3을 또 거쳐서 갔을 때 더 최소 비용이 나올 수 있기 때문이다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define MAX 5000   int main(void) {     int N, M, a, b, c, i, j, k;     freopen("input.txt", "rt", stdin);     scanf("%d %d", &N, &M);     vector<vector<int> > dis(N + 1, vector<int>(N + 1, MAX));     for (i = 1; i <= M; i++) {         scanf("%d %d %d", &a, &b, &c);         dis[a][b] = c;     }       for (i = 1; i <= N; i++)         dis[i][i] = 0;       for (k = 1; k <= N; k++) {         for (i = 1; i <= N; i++) {             for (j = 1; j <= N; j++) {                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);             }         }     }          for (i = 1; i <= N; i++) {         for (j = 1; j <= N; j++) {             if(dis[i][j] >= 5000)                 printf("M ");             else                 printf("%d ", dis[i][j]);         }         puts("");     }       return 0; } Colored by Color Scripter

cs

line 12) 최소 비용을 구해야 하므로 이동할 수 없는 경로는 비용을 5000으로 설정

     (최대 도로의 수가 200, 최대 거리 비용이 20이므로, 200 x 20 = 4000에서 넉넉하게 5000으로 설정)

line 13~16) 인접행렬 정보 입력

line 21~28) Floyd-Warshall 알고리즘이 동작하는 코드이다.

line 21) 1번 정점부터 N번 정점까지를 중간에 거쳐서 방문해볼 것이다.

line 24) k == i 일 경우 자기 변화가 없으므로 continue

line 25) i부터 j까지의 최소 비용은 

     기존 거리의 최소 비용과 기존 거리에 k정점을 거쳐 갔을 경우 비용의 min

#. Teach code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include<bits/stdc++.h> using namespace std; int main(){     ios_base::sync_with_stdio(false);     int n, m, a, b, c;     cin>>n>>m;     vector<vector<int> > dis(n+1, vector<int>(n+1, 5000));     for(int i=1; i<=n; i++) dis[i][i]=0;     for(int i=1; i<=m; i++){         cin>>a>>b>>c;         dis[a][b]=c;         }     for(int k=1; k<=n; k++){         for(int i=1; i<=n; i++){             for(int j=1; j<=n; j++){                 if(dis[i][j]>dis[i][k]+dis[k][j]){                     dis[i][j]=dis[i][k]+dis[k][j];                 }             }         }     }     for(int i=1; i<=n; i++){         for(int j=1; j<=n; j++){             if(dis[i][j]==5000){                 cout<<"M ";             }             else cout<<dis[i][j]<<" ";         }         cout<<endl;     }       return 0; } Colored by Color Scripter

cs

#. Result

  - Input --------------------------------------------------------

5 8

1 2 6

1 3 3

3 2 2

2 4 1

2 5 13

3 4 5

4 2 3

4 5 7

------------------------------------------------------------------

  - Output --------------------------------------------------------

0 5 3 6 13 

M 0 M 1 8 

M 2 0 3 10

M 3 M 0 7

M M M M 0

------------------------------------------------------------------