플로이드 최단 경로 알고리즘

플로이드 최단 경로 알고리즘

💡

모든 정점 쌍에 대해 최단 거리를 구할 때 쓰는 알고리즘

---

개요

board[u][v]

정점 u에서 정점 v까지의 최단거리를 저장

---

최단 거리를 찾는 방법

정점 u에서 정점 v까지 바로 가는 거리를 w(u, v)라고 하자

이 때, u→a→v를 가는 거리가 u→v 거리보다 짧다면 갱신하는 방식이다.

---

코드

public class 플로이드 {
    static int board[][];

    static void floyd() {
        // 자기 자신의 거리는 0
        for (int i = 0; i < board.length; i++) {
            board[i][i] = 0;
        }

        // 거리 계산하기
        for (int k = 0; k < board.length; k++) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    board[i][j] = Math.min(board[i][j], board[i][k] + board[k][j]);
                }
            }
        }
    }

    public static void main(String[] args) {

    }
}

---

최단 경로를 찾는 방법

via[u][v]

기본값은 -1을 가진다. 이는 u→v 의 경로가 가장 짧다는 것이다.

중간에 k라는 경유지를 거치는 경로를 갱신하면 via[u][v]는 k가 된다.

경로가 갱신 될 때 마다 바뀌므로 정확한 경로를 찾기 위한 작업이 필요하다.

reconstruct

u→v 경로를 찾아내는 메소드

u→v를 한 번에 갈 수 있다면

• 경로에 u 삽입

• 경로에 v 삽입

u→v 가 k를 경유한다면 다음 경우가 생긴다.

1. u→k
   • u→k 를 매개변수로 하여 reconstruct를 호출한다.

2. 중복구간 제거
   • u→k 호출, k→v 호출할 때 결과적으로 k가 2번 들어가게 되므로, u→k 경로 계산 후 마지막 경로(k노드 방문)를 제거한다

3. k→v
   • k→v 를 매개변수로 하여 reconstruct를 호출한다.

---

코드

import java.util.Arrays;
import java.util.List;

public class 플로이드 {
    // u에서 v까지 가는 가중치, 간선이 없으면 INF
    static int board[][];

    // u에서 v까지 가는 최단 경로를 경유하는 점 중 가장 번호가 큰 정점
    static int via[][];

    static void floyd() {
        // 자기 자신의 거리는 0
        for (int i = 0; i < board.length; i++) {
            board[i][i] = 0;
            Arrays.fill(via[i], -1);
        }

        // 거리 계산하기
        for (int k = 0; k < board.length; k++) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    via[i][j] = k;
                    board[i][j] = Math.min(board[i][j], board[i][k] + board[k][j]);
                }
            }
        }
    }

    static void reconstruct(int u, int v, List<Integer> path) {
        // 직접 가는게 가장 빠른 경우
        if (via[u][v] == -1) {
            path.add(u);
            if (u != v) {
                path.add(v);
            }
        }

        else {
            // u->v 경로 중 번호가 가장 큰 정점
            int w = via[u][v];
            // u->w 의 경로 찾기
            reconstruct(u, w, path);

            // w가 겹치므로 한 번 제거
            path.remove(path.size() - 1);

            // w->v 의 경로 찾기
            reconstruct(w, v, path);
        }
    }

    public static void main(String[] args) {

    }
}

Uploaded by N2T