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

Charbs·2025년 2월 7일

DP Java algorithm 다이나믹프로그래밍 알고리즘 최단경로 플로이드워셜

algorithm

목록 보기

34/37

모든 쌍 최단경로

모든 노드들 사이의 최단경로를 구하는 알고리즘

시간복잡도

$O(N^3)$
인접행렬의 다익스트라 알고리즘은 플로이드 워셜과 동일한 $O(N^3)$ 이지만,
희소그래프이면 인접리스트로 구현한 다익스트라를 N번 수행하는 경우는 $O(N^3)$ 보다 작기 때문에
만약 $O(N^3)$ 으로 시간초과가 난다면 다익스트라를 N번 돌려서 모든 정점간의 거리를 구하자.

음의 가중치

다익스트라는 그리디 알고리즘이기 때문에 음의 가중치는 처리하지 못했다.

하지만 플로이드 워셜은 모든 경우를 다 고려하기 때문에 음의 가중치도 처리 가능하다

플로이드-워셜

원리 - DP

부분문제 정의

경유지 활용

플로이드-워셜 알고리즘은 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해,
s와 e 사이의 노드인 m에 대해 (s에서 m까지 가는 데 걸리는 최단거리)와
(m에서 e까지 가는 데 걸리는 최단거리)를 이용한다.

임의의 노드 s 부터 e 까지 가는데 걸리는 최단거리를 d[s][e]라고 하자.
(처음에 d[s][e]의 값은 노드 s와 노드 e가 직접적으로 연결되어 있다면 그 노드의 가중치만큼, 그렇지 않다면 무한(INF)로 초기화한다.)
이 d[s][e]를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 d[s][e]에 저장되어 있는 값과, d[s][m]+d[m][e]의 값을 비교한다.
이 때 d[s][m]+d[m][e]의 값이 현재의 d[s][e] 값보다 작으면, d[s][e]를 d[s][m]+d[m][e] 의 값으로 업데이트한다.

출처-나무위키
나무위키가 설명을 잘해놨네.

의사코드

D[i][j] = 정점 i에서 정점j로의 최소비용
AllPairsShortest(D[][])
	FOR k in 1 -> n
    	FOR i in 1 -> n  (단, i != k)
        	FOR j in 1 -> n  (단, j!=k, j!=i)
            	D[i][j] <- min(D[i][k] + D[k][j], D[i][j])

Line 1 의 for-루프는 k가 1에서 n까지 변하는데, 이는 경유 가능한 정점을 1부터 n까지 확장 하는 것
Line 2~3 : 점들의 각 쌍을 하나씩 고려하기 위한 루프 (단, i=j 또는 i=k 또는 j=k 의 경우 제외)
Line 4 : 각 정점의 쌍 i-j에 대해 i에서 j까지의 거리가 k를 포함하여 경유하는 경로으 ㅣ거리, 즉, D[i][k] + D[k][j]와 정점 {1,2,...,(k-1)} 만을 경유 가능한 점들로 고려하여 계산된 최단 경로의 거리 D[i][j]가 짧은지를 결정하여 D[i][j]를 갱신한다.

java 코드

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

class Main {
    
    static int N, M;
    static int[][] mat;
    static final int INF = 100_000_001;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());        // 도시의 수
        M = Integer.parseInt(br.readLine());        // 버스의 수
        
        mat = new int[N+1][N+1];
        
        for (int n=1; n<=N; n++) {
            Arrays.fill(mat[n], INF);
            mat[n][n] = 0;
        }
        
        StringTokenizer st = null;
        for (int m=0; m<M; m++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            
            mat[a][b] = Math.min(mat[a][b], c);
        }
        
        floyd();
        
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                int value = mat[i][j];
                sb.append(value == INF ? 0 : value).append(" ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb);
        
    }
    
    static void floyd() {
        for (int k=1; k<=N; k++) {       // 경유지
            for (int i=1; i<=N; i++) {       // 출발지
                for (int j=1; j<=N; j++) {      // 도착지
                    if (mat[i][k] == INF || mat[k][j] == INF) continue;     // 연결이 없는 경우 건너뜀
                    int s2e = mat[i][j];        // 기존 경로
                    int s2m2e = mat[i][k] + mat[k][j];      // 경유지를 거쳐간 경로
                    mat[i][j] = Math.min(s2e, s2m2e);       // 업데이트
                }
            }
        }
    }
}