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

다익스트라 VS 플로이드 워셜

다익스트라 알고리즘은

한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우

사용할 수 있는 최단 경로 알고리즘이다.

 

플로이드 워셜 알고리즘은

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

사용할 수 있는 알고리즘이다.

 

다익스트라의 경우, 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 그리디 알고리즘에 속한다.

 

플로이드 워셜의 경우 또한, 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라와의 차이점이다. 다이나믹 프로그래밍에 속한다.

노드의 개수가 N개 일 때 알고리즘상으로 N번의 단계를 수행하며, 각 단계마다 $O(N)$의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서, 플로이드 워셜 알고리즘의 총시간 복잡도는 $O(N^3)$이다. 

 

 

다익스트라 알고리즘에서는 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했다. 반면, 플로이드 워셜 알고리즘은 이와 다르게 2차원 리스트에 최단 거리 정보를 저장한다. 모든 노드에 대하여 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다. 이때, 2차원 리스트를 처리해야 하므로 N번의 단계에서 $O(N^2)$의 시간이 소요되는 것이다.

---

플로이드-워셜

 

매 단계에서는 해당 노드를 거쳐가는 경우를 고려한다.

예를 들어 1번 노드에 대해서 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려한다. A→1번 노드→B로 가는 비용을 확인한 후, 최단 거리를 갱신하는 것이다. 현재 최단 거리 테이블에 A→B의 비용이 3으로 저장되어 있을 때, A에서 1번 노드를 거쳐 B로 이동하는 비용이 2라는 것이 밝혀지면, A→B의 비용을 2로 갱신하는 것이다.

따라서, 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1 개의 노드 중에서 서로 다른 노드 (A,B)쌍을 선택한다. 이후, A→1번→B의 비용을 확인한 뒤에 최단 거리를 갱신한다. 즉, $_{N-1}P_2$개의 쌍을 단계마다 반복해 확인하는 것이다. 이때, $O(_{N-1}P_2)$는 $O(N^2)$으로 볼 수 있기에, 전체 시간 복잡도가 $O(N^3)$이 되는 것이다. 

 

k번의 단계에 대한 점화식은 다음과 같다. $$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$

다음 그림을 통해 구체적인 예시를 확인해 보자.

 

위와 같은 그래프가 있을 때, 아래와 같이 초기 테이블을 설정할 수 있다.

행이 출발 노드, 열이 도착 노드이다. 연결되지 않은 간선(Edge)는 INF를 넣는다.

2차원 리스트에서 각 값에 해당하는 $D_{ab}$는 “a에서 b로 가는 최단 거리"이다.

 

 

첫 번째 단계에서는 단순히 1번 노드를 거쳐 가는 경우를 고려한다. 계산해야할 구체적인 값들은 다음과 같다.

$D_{23} = min(D_{23},D_{21}+D_{13})$

$D_{24} = min(D_{24},D_{21}+D_{14})$

$D_{32} = min(D_{32},D_{31}+D_{12})$

$D_{34} = min(D_{34},D_{31}+D_{14})$

$D_{42} = min(D_{42},D_{41}+D_{12})$

$D_{43} = min(D_{43},D_{41}+D_{13})$.

이렇게 6가지($_3P_2$) 식을 모두 계산해서 값을 갱신하면 다음과 같이 테이블이 바뀌게 된다.

 

 

다음으로 2번 노드를 거쳐가는 경우를 계산하여(2번을 제외한 1, 3, 4번 노드에서 2개의 노드 선택) 테이블을 갱신하면 다음과 같다. 

 

 

위와 같은 방식으로 모든 노드에 대해 테이블을 갱신하면, 최종적으로 다음과 같은 테이블이 나오게 된다.

이 테이블에 기록되어 있는 내용이 모든 노드에서 모든 노드로 가는 최단 거리 정보이다. $D_{13}$은 8의 값을 가지고 있는데, 이는 1번 노드에서 3번 노드로 가는 최단 거리가 8이라는 의미이다.

---

구현

자바를 이용하여 이를 구현해보면 코드는 다음과 같다.

import java.util.*;

public class Main{
	public static final in INF = (int)1e9; //INF값이 무한을 의미
    public static int node, edge; //노드의 개수(node), 간선의 개수(edge)
    public static int[][] graph = new int[501][501]; //노드의 개수는 최대 500개라 가정, 2차원 배열
    
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
        
        node = sc.nextInt();
        edge = sc.nextInt();
        
        for(int i=0;i<501;i++)
        	Arrays.fill(graph[i], INF); //최단거리 테이블을 모두 INF로 초기화
        
        for(int a=1;a<=node;a++)
        	for(int b=1;b<=node;b++)
            	if(a==b)
                	graph[a][b] = 0; //자신에서 자신으로 가는 비용=0 으로 초기화
        
        for(int i=0;i<edge;i++){
        	int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt(); //a에서 b로 가는 비용이 c
            graph[a][b] = c;
        }
        
        for(int k=1;k<=node;k++) //점화식에 따라 플로이드 워셜 알고리즘 수행
        	for(int a=1;a<=node;a++)
            	for(int b=1;b<=node;b++)
                	graph[a][b] = Math.min(graph[a][b], graph[a][k]+graph[k][b]);
                    
        for(int a=1;a<=node;a++){
        	for(int b=1;b<=node;b++){
            	if(graph[a][b]==INF) //도달할 수 없는 결루, INFINITY 출력
                	System.out.println("INFINITY");
                else
                	System.out.println(graph[a][b]+" ");
            }
            System.out.println();
        }
    }
}