[알고리즘] 그래프 - 플로이드 와샬

 컴퓨터 알고리즘에서 플로이드 혹은 플로이드 와샬 알고리즘은 임의의 시작점과 종료점간의 최단 경로를 구하는 알고리즘이다.

[다익스트라]와는 다르게 모든 정점에 대하여 한번에 경로를 구할 수 있는 장점이 있다. 하지만 최단 경로를 구하기 위해서는 정점의 개수 N에 대하여 O(N^3)의 시간 복잡도를 가지게 되므로, 실제 문제에 적용할 수 있는 N의 크기는 1초 1억(1e8) 대비하여 N이 100정도이다. 만약 N <= 1000인 경우 N^3이 10^9가 되며 약 10초 정도의 시간을 잡아야 한다.

 알고리즘의 요점은 정점 i에서 j로 가는 경로에서 임의의 정점 k를 거쳐가는 것이 빠른가, 아닌 것이 빠른가를 확인하는 것이다.

 즉, 임의의 정점 i, j, k(1 <= i, j, k <= N)에 대해, 기존 i->j 경로와 i->k->j 경로중 가까운 것을 최단 경로로 저장한다. 코드의 경우 아래와 같이 나타나게 된다.

for(int k = 1; k <= N; k++)
	for(int i = 1; i <= N; i++)
		for(int j =1; j <= N; j++)
			cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);

 

 또한 각 경로 i, j에 대하여 최단 경로를 출력하기 위해선, 최단 거리 갱신시에 직전 노드 k를 저장함으로써 나중에 이 경로를 복구할 수 있다.

int cost[N][N];
int path[N][N];

for(int k = 1; k <= N; k++){
  for(int i = 1; i <= N; i++){
    for(int j = 1; j <= N; j++){
      if(cost[i][j] > cost[i][k]+cost[k][j]){
        cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]);
        path[i][j] = k;
      }
    }
  }
}

void find(vector<int>& way, int i, int j){
  if(!path[i][j]){
    way.push([i, j]);
    return;
  }
  find(i,path[i][k]);
  way.pop()
  find(path[k][j],j);
}

vector<int> result;
find(result, 4, 5);