[Java] 플로이드 워샬

1. 플로이드 워샬이란?

 

• 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘.
• 시간복잡도 : O(N^3)

 

Dijkstra와 달리

 

• 모든 노드 쌍에 대한 최단 거리를 구하고,
• 음의 가중치를 가지는 그래프에서도 쓸 수 있다!

 

---

2. 구현

 

DP로 접근하기 위해 부분 문제를 정의해야 한다.

 

• s에서 e까지 가는 데 걸리는 최단거리는 (s->e) 또는 (s->m→e)이다.
  • (s->m→e) = s에서 m까지 가는 데 걸리는 최단거리 + m에서 e까지 가는 데 걸리는 최단거리

 

int INF = 1000000; // 도달할 수 없음을 의미 (구체적인 값은 문제 따라서 다름)
int[][] graph; // 그래프를 나타내는 2차원 배열
int n; // 노드의 개수

public void floydWarshall() {
    // 모든 정점에서 모든 정점으로 가는 최소 비용을 INF로 초기화
    for(int i=0; i<n; i++) {
        Arrays.fill(graph[i], INF);
        graph[i][i] = 0; // 자기 자신으로 가는 비용은 0
    }

    // 각 정점을 경유지로 가정하고 모든 정점 간의 최소 비용을 찾음
    for(int k=0; k<n; k++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

n개의 노드를 가진 그래프에서 플로이드 워샬 알고리즘을 통해 각 노드 간의 최단 거리를 구하는 예시 코드다.

 

INF는 무한을 의미하는 값으로 설정하였고, graph는 그래프를 나타내는 2차원 배열입니다.

 

플로이드-워샬에서 핵심 아이디어는 경유지를 하나씩 추가해 가며 비용을 최적화하는 것이다.

 

마지막 경유지를 추가하는 시점에서는 모든 쌍에 대한 최단 거리를 알 수 있다.

 

점차 시작점에서 경유지로 가는 경로와 경유지에서 도착점으로 가는 경로의 거리가 점차 최적화된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class FloydWarshallTest {

    static final int INF = 1000000;
    static int[][] dp;
    static int n, m; // 노드의 수, 간선의 수
    public static void main(String[] args) throws Exception {
        init();
        solve();
    }

    static void init() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dp = new int[n][n];
        for(int i=0; i<n; i++) {
            Arrays.fill(dp[i],  INF);
            dp[i][i] = 0;
        }

        int from ,to;
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            dp[from][to] = Integer.parseInt(st.nextToken()); // 간선 정보 입력
        }
    }

    static void solve() {
        for(int k=0; k<n; k++) { // 경유지
            for(int i=0; i<n; i++) { // 시작점
                for(int j=0; j<n; j++) { // 도착점
                    if(dp[i][k]+dp[k][j] < dp[i][j]) {
                        dp[i][j] = dp[i][k] + dp[k][j];
                    }
                    print(i, j);
                }
            }
        }
    }

    static void print(int curY, int curX) {
        StringBuffer sb = new StringBuffer();
        for(int y=0; y<n; y++) {
            for(int x=0; x<n; x++) {
                if(y==curY && x==curX) sb.append("* ");
                else if(dp[y][x] == INF) sb.append("~ ");
                else sb.append(dp[y][x] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

}

4 6
0 1 3
0 2 6
1 2 2
1 3 1
2 3 5
2 0 3

for(int k=0; k<n; k++) { // 경유지
    for(int i=0; i<n; i++) { // 시작점
        for(int j=0; j<n; j++) { // 도착점

for문의 순서에 주의하자.

 

경유지부터 선택해야 한다.

 

---

 

 

알고리즘	용도	설명	표현	시간복잡도	기타
Prim	최소 신장 트리	가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘.	인접 리스트, 인접 행렬	FOR : O(V^2) PQ : O(ElogE)	무방향
Kruskal	최소 신장 트리	가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘.	간선 리스트	O(ElogE + V)	무방향
Dijkstra	최소 경로	음의 가중치가 없는 그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘.	인접 리스트, 인접 행렬	FOR : O(V^2) PQ : O(ElogE)	음의 가중치 X
Bellman-Ford	최소 경로	그래프의 한 정점에서 다른 정점들까지의 최단 거리 비용을 구하는 알고리즘.	간선 리스트	O(VE)	음의 가중치 O
Floyd-Warshall	최소 경로	모든 정점 사이의 최단 거리 비용을 구하는 알고리즘.	인접 행렬	O(V^3)	음의 가중치 O 단, 음수 사이클 X

 

---