📌 About

Dijkstra 알고리즘이 하나의 정점에서 다른 정점들로 가는 최단 거리를 구하는 알고리즘이라면 Floyd-Warshall 알고리즘은 모든 정점에서 다른 모든 정점들로 가는 최단 거리를 구하는 알고리즘이다.

📌 Algorithm

Step 1. Graph를 초기화한다. (Self = 0, Null = INF)

Step 2. Node n번을 경유할 때 더 짧게 갈 수 있는 경우를 업데이트한다. (모든 node를 탐색)

📌 Java Code

private static int N;
private static int[][] infos;

private static void floydWarshall() {
    for (int mid = 1; mid <= N; mid++)
        for (int start = 1; start <= N; start++)
            for (int end = 1; end <= N; end++) {
                if (infos[start][end] > infos[start][mid] + infos[mid][end])
                    infos[start][end] = infos[start][mid] + infos[mid][end];
            }
}

📌 Example

Step 1. Graph를 초기화한다.

N-to-N은 0 이다.

이웃하지 않으면 INF 이다.

Step 2-1. Node 1을 경유하는 경우를 탐색한다.

3 → 1 → 2의 비용은 10이다.

기존의 3 → 2의 비용은 INF이다.

더 작은 값인 10을 저장한다.

5 → 1 → 3의 비용은 10이다.

기존의 5 → 3의 비용은 INF이다.

더 작은 값인 10을 저장한다.

5 → 1 → 4의 비용은 8이다.

기존의 5 → 4의 비용은 INF이다.

더 작은 값인 8을 저장한다.

Step 2-2. Node 2를 경유하는 경우를 탐색한다.

5 → 2 → 4의 비용은 6이다.

기존의 5 → 4의 비용은 8이다.

더 작은 값인 6을 저장한다.

Step 2-3. Node 3을 경유하는 경우를 탐색한다.

1 → 3 → 5의 비용은 4이다.

기존의 1 → 5의 비용은 10이다.

더 작은 값인 4를 저장한다.

Step 2-4. Node 4를 경유하는 경우를 탐색한다.