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

플로이드-워셜(Floyd–Warshall)

모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘
== 모든 정점을 하나씩 중간 경유지로 허용해보며, 최단 경로를 갱신하는 알고리즘

 

언제 사용하는가?

• 정점의 수가 크지 않을 때 (보통 <= 500)
• 모든 정점 쌍 최단 거리가 필요할 때
• 음수 간선이 있을 때 (단, 음수 사이클은 안 됨)

핵심 아이디어

중간 정점을 하나씩 추가해가면서
i -> k -> j로 가는 게 i -> j로 직접 가는 것보다 짧은가?를 확인한다.

 

핵심 반복 구조 수식 (3중 for문)

// k -> 거쳐갈 수 있는 중간 정점 집합을 하나씩 늘려가는 것

for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] > dist[i][k] + dist[k][j]) {
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

 

사용 예제

• 도시 간 최소 거리 (백준 11404 https://www.acmicpc.net/problem/11404)
• 네트워크 최소 비용
• 사이클 판별
• 최단 거리 행렬 만들고 싶을 때
• 그치만, n이 크면 불가능 !!