[그래프] 플로이드 와샬 알고리즘

플로이드 와샬

- '모든 정점'으로부터 다른 '모든 정점'까지 이동하는 최단 경로를 구하는 알고리즘

- 다익스트라와의 차이점은 특정한 하나의 정점이 아닌 '모든 정점'이라는 것입니다.

- 해당 알고리즘은 기본적으로 '특정 노드를 거쳐가 다른 노드로 이동'이라는 특징이 있습니다. (k - i - j)

- 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것!

 

www.acmicpc.net/problem/11404

11404번: 플로이드

 

public static void calculateMinPrices() {
    for(int k=1; k<N+1; k++) {
        for(int s=1; s<N+1; s++) {
            for(int e=1; e<N+1; e++) {

                minPrices[s][e] = Math.min(minPrices[s][e],
                            minPrices[s][k] + minPrices[k][e]);
            }
        }
    }
}

 2차원 배열 minPrices는 '지금까지 계산된 최소 비용'을 나타냅니다. 3중 for문으로 구성된 것은 위에서 언급한 '거쳐가는 정점'을 기준으로 했기 때문입니다.

 

 D[s][e] = D[s][k] + D[k][e] 란,

[s정점에서 k정점까지 이동한 최소비용] + [k정점에서 e정점까지 이동한 최소 비용]이 바로

 s정점에서 e정점까지 이동한 비용을 뜻합니다.

 

여기서 매번 최소값은 D[s][e]에 저장한다면 모든 정점으로부터의 최단 경로를 구할 수 있습니다.