플로이드 와샬 알고리즘이란?

알고리즘 문제를 풀다가 플로이드 와샬 알고리즘을 접해서 정리해보려고 한다!!
플로이드와 와샬 알고리즘이란??

플로이드 와샬 알고리즘

• 최단 거리를 구할 수 있는 알고리즘
• 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구한다.
• 모든 쌍을 표현하는 행렬(이차원 배열)을 선언하고 다이나믹 프로그래밍 방식으로 각각의 원소들(각 쌍의 최단거리)을 업데이트 해나간다.업데이트 기준 👉 현재 거쳐가는 정점
• 거쳐가는 정점을 기준으로 알고리즘을 수행한다.
  • i 에서 j 로 가는데 해당 정점을 경유해서 가는 것이 더 빠르다면 그 정점을 거쳐서 가는걸로 업데이트 한다.

진행 과정

• i행과 j열의 원소인 (i, j) 원소는 정점i로부터 정점j까지의 최단 경로를 뜻한다.
• Dynamic Programming 방식으로 진행된다.

  • 점화식

    • 👉 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
    • 정점 i에서 정점 n을 거쳐서 정점 j로 갈 때, n을 거쳐 가는 것이 더 최단경로일 경우 업데이트 한다.
    • 이렇게 거쳐갈 정점을 차례대로 모두 검사하여 업데이트 해나간다.

    EX)
    💁 정점 1을 거쳐갈 때

  • 기존의 (i,j)의 원소값 보다 (i, 1) + (1+j)의 값이 더 작으면 이 값으로 업데이트해주고, 아니면 그대로 둔다.

코드 ( 출처 : 나동빈님 블로그)

//FloydWarshall
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];

🐥 3중 for문을 이용하기 때문에 시간 복잡도는 O(n^3)이다.