[개념] 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

# 플로이드-워셜 알고리즘

• 모든 정점 사이의 최단 경로를 구하는 알고리즘
• 순환만 없다면 음수 가중치도 가능
• 동적계획법으로 접근
  • dist[i][j] = Math.min( ~ , ~ ) 형태를 가짐
• N개의 정점을 가진다고 할 때, 모든 정점으로 가는 최단 거리를 확인하므로 시간복잡도 = O(N^3)
  
  • N이 200~300 이하인 경우에만 가능

---

# 코드

1. INF 값으로 세팅

• public static final int INF = 1_000_000_000;
• INF 값을 Integer.MAX_VALUE로 설정하는 경우, 연산 과정에서 overflow 발생하는 문제 종종 있음
  => 잘 확인해서 INF 값 적당히 크게 설정하기

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        dist[i][j] = INF;
    }
}

 

2. 최단 거리 구하기

• k = 경유지, i = 출발지, j = 도착지

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