[Algorithm] 플로이드 와샬(Floyd Warshall)

플로이드 와샬

하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다익스트라와는 다르게 플로이드 와샬은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 또한 다이나믹 프로그램에 기반을 두고 있다.

 

알고리즘

핵심은 "X에서 Y로 가는 최소 비용 vs X에서 선택된 노드로 가는 비용 + 선택된 노드에서 Y로 가는 비용" 중 최소값을 선택하는 것이다.

즉, 점화식으로 나타내자면 distance[i, j] = min(distance[i, j], distance[i, n] + distance[n, j])

int INF = 1000000;

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

// 시간복잡도 V^3
for(int k = 0; k < 4; k++)  // k 는 거쳐가는 정점
  for(int i = 0; i < 4; i++)  // i 는 행 (출발 정점)
    for(int j = 0; j < 4; j++)  // j 는 열 (도착 정점)
      if (a[i][k] + a[k][j] < a[i][j])  // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
        a[i][j] = a[i][k] a[k][j];

 

자세한 과정은 아래의 블로그를 참고하자:)

 

 

Reference

https://blog.naver.com/ndb796/221234427842

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