플로이드 워셜 알고리즘 : 모든 출발지에서 다른 모든 출발지까지 최단 경로 계산

플로이드 워셜

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계에서 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.

플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장하며 동적계획법(DP) 유형에 포함된다.

 

각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인한다. a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 체크한다.

 

따라서 점화식은 다음과 같다.

---

동작과정

인접한 노드만 확인하여 최단 거리 테이블을 초기화한다.

1번 노드(k)를 거쳐가는 경우를 고려하여 테이블을 갱신한다. 이후 반복하여 n번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.

구현

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

public class Main {
    static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    static int n, m;
    static int[][] graph = new int[501][501]; // 노드의 개수를 최대 500개라고 가정

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 501; i++)
            Arrays.fill(graph[i], INF);

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++)
            for (int b = 1; b <= n; b++)
                if (a == b) graph[a][b] = 0;

        // 각 간선에 대한 정보 입력받기
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }

        // 점화식
        for (int k = 1; k <= n ; k++)
            for (int a = 1; a <= n ; a++)
                for (int b = 1; b <= n ; b++)
                    graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);


        // (생략) 

    }
}

 

플로이드 워셜 알고리즘의 시간복잡도는 O(N³) 이다. 따라서 노드와 간선이 많은 문제에는 적합하지 않다.