플로이드-워셜 (Floyd-Warshall)

1. 플로이드-워셜 알고리즘

다익스트라 알고리즘은 '한 특정 지점에서 다른 특정 지점까지의 최단경로를 구할때' 쓰는 알고리즘이다. 이와는 다르게 플로이드-워셜 알고리즘은 '모든 지점에서 다른 모든지점까지의 최단경로를 모두 구할때' 쓰는 알고리즘이다.

 

2. 플로이드-워셜 알고리즘의 시간복잡도

생각보다 단순하게도 O(N^3) 의 시간 복잡도를 가진다. 다만 N^3 이라는 것 자체가 N이 커질수록 기하 급수적으로 커지기 때문에 노드의 개수가 N개일때, 이 N의 제한이 조금 작을때만 사용이 가능하다.

 

 

플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 다이나믹 프로그래밍의 일부로 볼 수 있다. 노드의 개수가 N개 라고 할때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트(배열) 을 갱신하기 때문이다. 이떄 구체적인 점화식은 다음과 같다.

Dab = min(Dab, Dak + Dkb)

a에서 b로 가는 최단경로는 그 자체의 값과 k를 들렀다가 가는 값 중에 작은 값을 취한다는 뜻이다.

다음의 예시로 단계별로 살펴보자.

위와 같은 그래프가 있다고 가정한다. 초기 상태인 step 0 에서는 연결된 간선은 그 값을 채워넣고 연결되지 않은 간선은 INF로 채운다. 또한 자기 자신에서부터 자신으로 가는 간선은 0으로 초기화 한다.

 

STEP 0)

	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	INF
3번	5	INF	0	4
4번	INF	INF	2	0

STEP 1)

1번 노드를 거쳐서 가는 모든 경우를 고려한다. 1번 노드를 제외한 2,3,4 노드에서 2개를 순서없이 선택하는 것이므로 6가지의 경우가 나온다. (2,3) , (2,4) , (3,2) , (3,4) , (4,2) , (4,3) 을 아까 봤던 점화식에 대입하여 갱신한다.

Dab = min(Dab, Dak + Dkb)

따라서 다음과 같이 바뀐다.

	1번	2번	3번	4번
1번	0	4	INF	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

STEP 2)

2번 노드를 거쳐서 가는 모든 경우를 따져본다. (1,3) , (1,4) , (3,1) , (3,4) , (4,1) , (4,3) 이 그 가짓수가 되고 이를 갱신한다.

	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	INF	INF	2	0

 

STEP 3)

3번노드에 대해서도 같은 과정을 거친다.

	1번	2번	3번	4번
1번	0	4	11	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

 

STEP 4) 

4번 노드에 대해서도 같은 과정을 거친다.

	1번	2번	3번	4번
1번	0	4	8	6
2번	3	0	7	9
3번	5	9	0	4
4번	7	11	2	0

이것이 최종 결과가 된다. 노드의 개수가 4개 이므로 단계도 4번 진행된다. 소스코드는 다음과 같다.

#include <iostream>
#include <algorithm>
#define MAX 1e9
using namespace std;

int n,m;
int map[501][501];

int main()
{
  freopen("input.txt","r",stdin);
  cin>>n>>m;
  for(int i=0;i<501;i++){
    fill(map[i],map[i]+501,MAX);
  }

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(i==j)
        map[i][j]=0;
    }
  }
  
  for(int j=0;j<m;j++){
      int a,b,c;
      cin>>a>>b>>c;
      map[a][b]=c;
  }

  for(int k=1;k<=n;k++){
    for(int a=1;a<=n;a++){
      for(int b=1;b<=n;b++){
        map[a][b]=min(map[a][b],map[a][k]+map[k][b]);
      }
    }
  }

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cout<<map[i][j]<<" ";
    }
    cout<<'\n';
  }
}