모든 지점의 최단 경로를 구하는 방법

플로이드 워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우에 사용할 수 있는 알고리즘입니다.

알고리즘

플로이드 워셜은 다음과 같은 점화식을 사용합니다.

$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

이 점화식을 기반으로 3중 반복문을 사용하면 쉽게 구현 할 수 있습니다.

• 이때 시간복잡도는 O(n^3)입니다.

의사코드

#include <iostream>
#include <vector>
#define INF 99999999
using namespace std;
int main(void) {
  int n,t; cin >> n >> t;
  vector v(n+1,vector(n+1,INF));
  for (int i=1;i<=n;i++) { //자기 자신의 거리 0으로 설정
    v[i][i]=0;
  }
  for (int i=0;i<t;i++) { //초기 값 입력
    int a,b,c; cin >> a >> b >> c;
    v[a][b]=c;
  }
  for (int k=1;k<=n;k++) { // 점화식
    for (int i=1;i<=n;i++) {
      for (int j=1;j<=n;j++) {
        v[i][j]=min(v[i][j],v[i][k]+v[k][j]);
      }
    }
  }
  for (int i=1;i<=n;i++) { // 출력
    for (int j=1;j<=n;j++) {
      if (v[i][j]!=INF) cout<<v[i][j]<<' ';
      else cout << "INF ";
    }
    cout<<'\\n';
  }
  return 0;
}