[DP] 플로이드-워샬(Floyd-Warshall) 알고리즘

 

모든 쌍 최단 경로 문제를 푸는 알고리즘

 

 

모든 쌍 최단 경로 문제

• 각 쌍의 점 사이의 최단 경로를 찾는 문제
• 풀이방법
  1. 다익스트라 알고리즘 O(n³)
  2. 플로이드 워샬 알고리즘 O(n³)

 

플로이드 워샬 알고리즘(Floyd-Warshall)

• 동적계획법 알고리즘
• 매우 간단하여 다익스트라 알고리즘보다 효율적
• 음의 간선이 존재해도 모든 최단 경로를 구할 수 있음 (다익스트라는 안됨)
• 귀납법으로 증명이 가능하다

 

 

간단한 원리

• 어떤 점을 경유하는 거리와 다이렉트 경로 중 작은값을 선택하여 갱신함
• D[2,3] 이라는 2부터 3의 거리가 있다면
  • 1을 경유하는 거리 D[2, 1] + D[1,3]
  • 원래거리 D[2,3]
  • D[2,3] = min( D[2,3],  D[2,1] + D[1,3] )
• 1을 경유하는 거리 비교 후 갱신, 2를 경유하는 거리 비교 후 갱신, ... , n을 경우하는 거리 비교 후 갱신
• 이렇게 해주면 최솟값이 무조건 나온다(귀납법 증명가능)

 

시간/공간 복잡도

• 시간: O(n³) -> 3중 for문
• 공간: O(n²) -> 2차원 배열 사용

 

자바코드

for (int k=1; k<=n; k++) {
  for (int i=1; i<=n; i++) {
    if (i==k) continue;
        
    for (int j=1; j<=n; j++) {
      if (j==k || j==i)continue;
        
      D[i][j] = Math.min(D[i][j], D[i][k]+D[k][j]);
    }
  }
}

• 굉장히 간단한 코드