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

플로이드 워셜이란?

최단 경로 담색 알고리즘 중 하나이다.

음수 사이클이 없는 경우에 사용할 수 있다.

모든 정점 간에 최단 경로를 구할 때 사용된다.

 

시간 복잡도 : Θ(N^3)

사용법

정점의 개수가 3개, 2를 거치는 경우

 

일단 N x N 예시의 경우는 3 x 3의 배열을 선언해주고 모든 칸을 매우 큰 값으로 초기화해준다.

 

1. 정점 1에서 시작하여 2를 거쳐 3에 도달하는 경로를 구한다

dist[1][3] = MIN(dist[1][3],dist[1][2]+dist[2][3])

 

2. 정점 1에서 시작하여 2를 거쳐 4에 도달하는 경로를 구한다

dist[1][4] = MIN(dist[1][4],dist[1][2]+dist[2][4])

 

3. 정점 3에서 시작하여 2를 거쳐 1에 도달하는 경로를 구한다

dist[3][1] = MIN(dist[3][1],dist[3][2]+dist[2][1])

 

4. 정점 3에서 시작하여 2를 거쳐 4에 도달하는 경로를 구한다

dist[3][4] = MIN(dist[3][4],dist[3][2]+dist[2][4])

 

5. 정점 4에서 시작하여 2를 거쳐 1에 도달하는 경로를 구한다

dist[4][1] = MIN(dist[4][2],dist[4][2]+dist[2][1])

 

6. 정점 4에서 시작하여 2를 거쳐 3에 도달하는 경로를 구한다

dist[4][3] = MIN(dist[4][3],dist[4][2]+dist[2][3])

 

이러한 방식으로 1을 거치는 경우, 2를 거치는 경우, 3을 거치는 경우, 4를 거치는 경우를 구해준다.

 

코드

i가 출발 정점, k가 도착 정점이며 j가 거치는 정점이다

for(int j=1;j<=N;j++){
    for(int i=1;i<=N;i++){
        for(int k=1;k<=N;k++){
            if(list[i][j]==Integer.MAX_VALUE||list[j][k]==Integer.MAX_VALUE||i==k) continue;
            list[i][k]=Math.min(list[i][j]+list[j][k],list[i][k]);
        }
    }
}