[알고리즘] 플로이드 와샬 알고리즘

플로이드 와샬 알고리즘은 다익스트라 알고리즘처럼 최단 경로를 구하는 알고리즘이다.

다익스트라 알고리즘은 출발 정점을 정하고 그 정점부터 가장 가까운 정점들을 선택해나가는데 비해,

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로 최단 경로를 구한다.

int INF = 1000000;

int a[4][4] = {
  { 0, 5, INF, 8 },
  { 7, 0, 9, INF },
  { 2, INF, 0, 4 },
  { INF, INF, 3, 0 }
};

for(int k = 0; k < 4; k++)  
  for(int i = 0; i < 4; i++)
    for(int j = 0; j < 4; j++
      if (a[i][k] + a[k][j] < a[i][j]) 
        a[i][j] = a[i][k] + a[k][j];

코드 출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

https://ansohxxn.github.io/algorithm/floyd/

 

첫번째 링크를 보면 동작 과정을 자세히 볼 수 있다. for문 순서를 외워야 한다.

바깥쪽부터 거쳐가는 정점, 출발 정점, 도착 정점 순으로 루프를 만들어야한다. 

거쳐가는 정점을 기준으로 하면 계산해야 할 양이 줄어들기 때문에 가장 바깥쪽에 거쳐가는 정점 기준 루프를 돌린다.

 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])

위 점화식을 사용해 모든 정점을 돌면서 최단 경로를 업데이트해준다.

삼중루프를 돌고 있으므로 시간 복잡도는 O(N^3)이다.