플로이드-워셜 (Floyd-Warshall) 알고리즘 정의 및 작동 원리, 자바로 구현해보기

플로이드-워셜 (Floyd-Warshall) vs 다익스트라 (Dijkstra)

	다익스트라	플로이드-워셜
사용 목적	단일 출발점 최단 경로를 찾음	모든 정점 쌍 간의 최단 경로를 찾음
가중치 제약	음의 가중치를 가진 간선을 처리할 수 없음	음의 가중치를 가진 간선을 처리할 수 잇음
기본 구조	그래프의 인접 리스트 혹은 인접 행렬을 사용함	그래프의 인접 행렬을 사용함
시간 복잡도	O(V+E)logV (우선 순위 큐를 사용했을 경우)	O($N^{3}$)
알고리즘 유형	그리드 알고리즘	동적 프로그래밍

 

플로이드-워셜 개요

플로이드-워셜은 a → b 로 가는 비용과 a → c → b 로 가는 비용 중에 더 적은 값을 최단 거리로 판단하는 알고리즘으로 다음과 같은 점화식을 가진다.

 

dp_ab= Math.min(dp_ab, dp_ac + dp_cb)

 

 

플로이드-워셜 동작 과정

1️⃣ 최단 거리를 저장하는 2차원 배열 dp에 자기 자신 노드로 가는 비용은 항상 0이므로 초기화해 준다.

2️⃣ 특정 노드에서 다른 노드로 가는 비용에 따라 dp 배열을 갱신한다. (연결되어있지 않은 경우에는 'INF'로 초기화한다.)

3️⃣ 1번 노드부터 순서대로 해당 노드를 중간에 거쳐서 가는 모든 노드 간의 최단 경로를 계산하고 dp 배열을 갱신한다.

 

 

1. 우선 dp 배열을 생성 후에 모든 값을 0으로 초기화 (과정 1️⃣), 노드 간의 연결 상태에 따라서 값을 초기화해 준다. (과정 2️⃣)

출발/도착	A	B	C	D
A	0	-1	INF	INF
B	INF	0	3	4
C	INF	-2	0	5
D	7	INF	INF	0

 

2. 특정 노드에서 출발해서 노드 A를 거쳐서 다른 모든 노드로 가는 최단거리를 본다. 출발 노드 본인을 제외하고, 노드 A를 제외하면 각 노드당 2개의 경로가 생긴다. 노드 A를 제외하고 총 3개의 노드가 존재하므로 2x3 = 6개의 연산이 진행된다.

 

dp_bc = Math.min(dp_bc, dp_ba + dp_ac)

dp_bd = Math.min(dp_bd, dp_ba + dp_ad)

dp_cb = Math.min(dp_cb, dp_ca + dp_ab)

dp_cd = Math.min(dp_cd, dp_ca + dp_ad)

dp_db = Math.min(dp_db, dp_da + dp_ab)

dp_dc = Math.min(dp_dc, dp_da + dp_ac)

 

위 6가지 연산을 진행하면서 dp 배열과 비교 후에 적은 값은 수정해 주면 된다. (과정 3️⃣) 

아래는 연산 결과와 dp 배열이 수정된 결과를 표로 나타냈다.

연산	dpnm	dpna + dpam	Math.min(dpnm, dpna + dpam)
dpbc = Math.min(dpbc, dpba + dpac)	3	INF + INF = INF	3
dpbd = Math.min(dpbd, dpba + dpad)	4	INF + INF = INF	4
dpcb = Math.min(dpcb, dpca + dpab)	-2	INF + -1 = INF	-2
dpcd = Math.min(dpcd, dpca + dpad)	5	INF + INF = INF	5
dpdb = Math.min(dpdb, dpda + dpab)	INF	7 + -1 = 6	6 (갱신)
dpdc = Math.min(dpdc, dpda + dpac)	INF	7 + INF = INF	INF

출발/도착	A	B	C	D
A	0	-1	INF	INF
B	INF	0	3	4
C	INF	-2	0	5
D	7	6 (갱신)	INF	0

 

3. 다음은 노드 B를 거치는 경우

연산	dpnm	dpnb + dpbm	Math.min(dpnm, dpnb + dpbm)
dpac = Math.min(dpac, dpab + dpbc)	INF	-1 + 3 = 2	2 (갱신)
dpad = Math.min(dpad, dpab + dpbd)	INF	-1 + 4 = 3	3 (갱신)
dpca = Math.min(dpca, dpcb + dpba)	INF	-2 + INF = INF	INF
dpcd = Math.min(dpcd, dpcb + dpbd)	5	-2 + 4 = 2	2 (갱신)
dpda = Math.min(dpda, dpdb + dpbd)	7	6 + 4 = 10	7
dpdc = Math.min(dpdc, dpdb + dpbc)	INF	6 + 3 = 9	9 (갱신)

출발/도착	A	B	C	D
A	0	-1	2 (갱신)	3 (갱신)
B	INF	0	3	4
C	INF	-2	0	2 (갱신)
D	7	6	9 (갱신)	0

 

4. 다음은 노드 C를 거치는 경우

연산	dpnm	dpnc + dpcm	Math.min(dpnm, dpnc + dpcm)
dpab = Math.min(dpab, dpac + dpcb)	-1	2 + -2 = 0	-1
dpad = Math.min(dpad, dpac + dpcd)	3	2 + 2 = 4	3
dpba = Math.min(dpba, dpbc + dpca)	INF	3 + INF = INF	INF
dpbd = Math.min(dpbd, dpbc + dpcd)	4	3 + 2 = 5	4
dpda = Math.min(dpda, dpdc + dpca)	7	9 + INF = INF	7
dpdb = Math.min(dpdb, dpdc + dpcb)	6	9 + -2 = 7	6

출발/도착	A	B	C	D
A	0	-1	2	3
B	INF	0	3	4
C	INF	-2	0	2
D	7	6	9	0

 

5. 다음은 노드 D를 거치는 경우

연산	dpnm	dpnd + dpdm	Math.min(dpnm, dpnd + dpdm)
dpab = Math.min(dpab, dpad + dpdb)	-1	3 + 6 = 9	-1
dpac = Math.min(dpac, dpad + dpdc)	2	3 + 9 = 12	2
dpba = Math.min(dpba, dpbd + dpda)	INF	4 + 7 = 11	11 (갱신)
dpbc = Math.min(dpbc, dpbd + dpdc)	3	4 + 9 = 13	3
dpca = Math.min(dpca, dpcd + dpda)	INF	2 + 7 = 9	9 (갱신)
dpcb = Math.min(dpcb, dpcd + dpdb)	-2	2 + 6 = 8	-2

 

마지막 노드 D까지 진행했으므로 최종적으로 각 노드에서 특정 노드까지의 최단 거리는 아래의 표와 같다.

출발/도착	A	B	C	D
A	0	-1	2	3
B	11 (갱신)	0	3	4
C	9 (갱신)	-2	0	2
D	7	6	9	0

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    /*
    4
    6
    1 2 -1
    2 3 3
    2 4 4
    3 2 -2
    3 4 5
    4 1 7	
    */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int CityCnt = Integer.parseInt(br.readLine());
        int BusCnt = Integer.parseInt(br.readLine());
		
        int[][] dp = new int[CityCnt+1][CityCnt+1];
		
        for (int i=1; i<=CityCnt; i++) {
            for (int j=1; j<=CityCnt; j++) {
                dp[i][j] = 50;
				
                if (i == j) dp[i][j] = 0;
            }
        }
		
        for (int i=0; i<BusCnt; i++) {
            st = new StringTokenizer(br.readLine());
			
            int start = Integer.parseInt(st.nextToken()); 
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
			
            // 중복된 길은 가중치가 낮은 걸로 설정
            if (dp[start][end] > 0) { 
                dp[start][end] = Math.min(dp[start][end], value);
            } else {
                dp[start][end] = value;
            }
        }
		
        for (int i=1; i<=CityCnt; i++) {
            for (int j=1; j<=CityCnt; j++) {
                for (int k=1; k<=CityCnt; k++) {
                    if (dp[j][k] > dp[j][i] + dp[i][k]) {
                        dp[j][k] = dp[j][i] + dp[i][k];
                    }
                }
            }
        }
		
        for (int i=1; i<=CityCnt; i++) {
            for (int j=1; j<=CityCnt; j++) {
                if (dp[i][j] == 50) System.out.print(0 + " ");
                else System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
}