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

그래프에서 정점 사이의 최단 경로를 구하는 방법

• 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 경우(1:1)
  • BFS, DFS
• 하나의 정점에서 다른 모든 정점까지의 모든 정점까지의 최단 경로를 구하는 경우(1:N)
  • 다익스트라, 벨만포드
• 하나의 목적지로만 가는 모든 최단 경로를 구하는 경우(N:1)
• 모든 최단 경로를 구하는 경우(N:N)
  • 플로이드 와샬

플로이드 와샬 정의

• 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘
  • 가중치가 양수 or 음수인 경우, 음의 사이클이 없는 그래프에서는 모든 정점 사이의 최단 거리 구하기 가능 (알고리즘을 한 번 수행할 때)
  • 그러나, 음의 사이클이 존재하는 그래프는 최단 거리 구하기 불가능 (알고리즘을 수행할 때마다 최단 거리 갱신)
• 2차원 배열을 이요하여 동적계획법(dp)으로 최적의 값 계산

플로이드 와샬 알고리즘 순서

1. 배열 초기화 arr[start][end]

   • 출발 지점과 도착지점이 동일하면 0
   • 출발 지점과 도착지점이 동일하지 않으면 무한

2. 가중치 입력

   • 문제에서 가중치의 개수(m) 주어짐
   • 출발 지점, 도착 지점, 가중치 입력 받아 배열에 저장

3. 출발 지점과 도착 지점 사이의 경유지를 통과하는 경우 탐색

   • 경유지를 통과하는 경우 거리가 더 빠르면 최단 거리 갱신
   • if (arr[i][j] > arr[i][k] + arr[k][j]) arr[i][j] = arr[i][k] + arr[k][j];

플로이드 와샬 동작 원리

시간 복잡도 O(n^3) => n이 500이하에서 가능 경유지를 통해서 갈 때의 가중치의 합이 더 작은 경우 최단 거리 갱신

void floyd(){
  for(int k = 1; k <= n; k++){ // 경유지 k
    for(int i = 1; i <= n; i++){ // 출발지점 i
      for(int j = 1; j <= n; j++){ // 도착지점 j
        if (arr[i][j] > arr[i][k] + arr[k][j])
            arr[i][j] = arr[i][k] + arr[k][j];
      }
    }
  }
}