플로이드 워셜(Floyd Warshall)

다익스트라는 한 지점에서 다른 지점으로의 최단 경로를 구하는 알고리즘이다. 

하지만, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 겨우에는 플로이드 워셜 알고리즘을 이용한다. 

두 알고리즘의 차이점을 확인해보면 아래와 같다. 

 

다익스트라의 경우에는

• 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택
• 해당 노드를 거쳐가는 경로를 확인하며 테이블을 갱신
• 한 지점에서 다른 지점에 대한 최단 거리이기 때문에 1차원 배열
• 모든 지점에 대해 반복하면 확인하기 때문에 그리디 알고리즘

플로이드 워셜의 경우에는

• 방문하는 노드에 대해서만 최단 거리를 확인
• 모든 지점에서 모든 지점이기 때문에 2차원 배열
• 노드의 갯수만큼 방문하며 확인하기 때문에 dp 알고리즘
• 시간 복잡도 `O(n^3)`

 

🔻 그림으로 확인

 

[0] 최단 거리 행렬 초기화

 

초기 그래프를 인접 행렬로 나타내면 아래와 같다. 

`INF`는 해당 노드에서 특정 노드까지의 경로가 존재하지 않는 경우이다. 

 

 

0	5	INF	8
7	0	9	INF
2	INF	0	4
INF	INF	3	0

 

 

 

 

[1] 1번 노드를 거쳐가는 경우

 

색칠한 부분만 갱신해주면 되는데 

이 상황에서 `i`에서 `j`로 가는 최소 거리라는 것은 

`i에서 1로 가는 비용 +  1에서 j로 가는 비용` 과  `i에서 j로 가는 최소 비용`을 비교하는 것이다. 

이를 그래프와 코드로 나타내면 아래와 같다.

 

 

0	5	INF	8
7	0	9	15
2	7	0	4
INF	INF	3	0

 

 

 

[2] 2번 노드를 거쳐가는 경우

 

 

0	5	14	8
7	0	9	15
2	7	0	4
INF	INF	3	0

 

 

 

[3] 3번 노드를 거쳐가는 경우

 

 

0	5	14	8
7	0	9	15
2	INF	0	4
5	10	3	0

 

 

 

[4] 4번 노드를 거쳐가는 경우

 

0	5	11	8
7	0	9	15
2	7	0	4
5	10	3	0

 

 

 

🔻 전체 코드 (java)

 

최단 거리 행렬 초기화

시작 지점과 도착 지점이 같은 경우 즉, 자기 자신으로 가는 경로의 경우에는 `0`

아직 최단 거리가 존재하지 않는 경우에는 `INF`

최단 거리를 확인한 경우에는 해당 값을 입력한다.

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

 

 

for문을 통한 행렬 갱신

중간 노드가 될 노드를 가장 바깥 for문의 변수로 지정한다. 

i와 j를 통해 모든 노드를 확인하며 k를 중간 노드로 설정할 때와 아닐 때의 값을 비교해 최단 거리로 갱신한다.

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]);
        }
    }
}