플로이드 와샬 알고리즘

모든 쌍 최단 거리 알고리즘 

단일 시작점 최단 거리 알고리즘인 다익스트라, 벨만 포드와 다르게 모든 쌍 최단 거리 알고리즘이다. 

음수 사이클이 없는 음수 가중치에서도 작동한다. 

 

 

vs 다익스트라, 벨만포드

단일 시작점 최단 거리 알고리즘을 모든 정점에서 실행하여도 모든 쌍 최단 거리 알고리즘을 구할 수 있다. 

하지만, 구현하기에 플로이드 워샬이 더 간단하다. 또한, 간선이 많은 경우에도 시간 복잡도가 더 낫다. 

 

모든 쌍 최단 거리 시간 복잡도 

다익스트라 O(V x ElgE)

벨만포드 O(V x VE)

플로이드 O(V^3) 

 

 

 

 

 

핵심 

1 dist[u][v]

2차월 배열의 dist[u][v]를 사용한다. 

u에서 v까지의 최단거리 유지

이동 불가능한 경우는 큰 수로 초기화하며 동일한 정점의 경우는 0으로 초기화한다. 

 

 

 

2 정점의 경유점들

u 에서 v까지 최단거리를 구하려고 한다. 

모든 정점들은 u, v최단 경로에 속하거나 속하지 않는 두 가지로 고려할 수 있다. 

따라서, 어떤 정점 k에 대해 dist[u][v] = min( dist[u][v], dist[u][k] + dist[k][v] ) 와 같이 식을 세울 수 있다. 

( 어떤 정점 k를 거치지 않거나, 거친 경우 )

 

 

 

3 과정 및 구현

모든 정점 k 에 대해 k를 거치거나 거치지 않을때를 고려해서 모든 쌍 최단 거리를 구해야 한다. 

 

 

정점 0을 거치거나 거치지 않았을 때, 

정점 0에서

    모든 정점까지의 최단 거리

정점 1에서

    모든 정점까지의 최단 거리

정점 2에서

    모든 정점까지의 최단 거리

.

.

.

=> 정점 0을 거치거나 거치지 않았을 때,  모든 쌍의 최단 거리가 갱신

 

 

정점 1 을 거치거나 거치지 않았을 때,

정점 0에서

    모든 정점까지의 최단 거리

정점 1에서

    모든 정점까지의 최단 거리

정점 2에서

    모든 정점까지의 최단 거리

.

.

.

=> 정점 0 or 1을 거치거나 거치지 않았을 때, 모든 정점 쌍의 최단 거리가 갱신

( 정점 0 거치거나 거치지 않았을때 최단 거리가 w에 이미 들어있었다. )

 

 

정점 2 을 거치거나 거치지 않았을 때,

정점 0에서

    모든 정점까지의 최단 거리

정점 1에서

    모든 정점까지의 최단 거리

정점 2에서

    모든 정점까지의 최단 거리

.

.

.

=> 정점 0 or 1 or 2을 거치거나 거쳤을때,  대해 모든 쌍 최단 거리 갱신

( 정점 0 or 1 거치거나 거치지 않았을때 최단 거리가 w에 이미 들어있었다. )

 

이 과정은 모든 정점에 대해 시도하면, 모든 가능한 정점 조합 중 모든 쌍 최단 거리를 구할 수 있게 된다. 

 

 

 
/* 
    w[i][j] : 정점 i에서 j까지 최단 거리(가중치), 경로가 없다면 매우 큰 수 
*/
static int[][] adj;
 
// 모든 쌍 최단 거리 알고리즘 
static void floyd(){
    
 
    for(int i = 0 ; i < V ; i++){
        w[i][i] = 0;
    }
    
    // 모든 정점 k를 거치거나 거치지 않거나 
    for(int k = 0 ; k < V ; v++){
        // 모든 쌍 i, j 의 최단 거리를 구한다. 
        for(int i = 0 ; i < V ; i++){
            for(int j = 0 ; j < V ; j++){
                w[i][j] = Math.min( w[i][j], w[i][k] + w[k][j]); 
            }
        }
    }
}