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

Floyd-Warshall 알고리즘 이란?

• 모든 노드간에 최단거리를 구하는 알고리즘
• 다익스트라, 벨만포드는 한 노드에서 모든노드까지의 최단경로
• Floyd-Warshall은 모든노드에서 모든노드까지의 최단 경로
• 벨만포드와 같이 가중치에 음수가 있어도 가능
• 시간복잡도 : O(V^3) (V:노드의 수)

• 위 그래프에서 1 -> 5의 최단경로는 1 -> 3 -> 4 -> 5 임
• 이 때, 중간지점을 4로 지정해 보면 (1 -> 4) + (4 -> 5) = 1 -> 5 가 항상 성립
• Floyd-Warshall은 이 논리를 사용
• 시작점 : s, 끝점 : e, 중간점 : k => dist[s][e] = min(dist[s][e], dist[s][k] + dist[k][e])
• k, s, e는 3중 for문을 통해 모든 경우의 수를 비교
  • O(V^3)의 시간복잡도를 갖게 됨

구현

https://www.acmicpc.net/problem/11404

• 이 문제를 Floyd-Warshall을 통해 해결하면서 구현해봄

코드

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

public class p11404 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());

        int[][] dist = new int[n + 1][n + 1];
        for(int i = 1 ; i <= n ; i ++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
            dist[i][i] = 0;
        }

        for(int i = 0 ; i < m ; i ++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if(dist[a][b] > c) {
                dist[a][b] = c;
            }
        }

        // i:중간점   j:시작점   k:끝점
        for(int i = 1 ; i <= n ; i ++) {
            for(int j = 1 ; j <= n ; j ++) {
                if(dist[j][i] == Integer.MAX_VALUE) continue;
                for(int k = 1 ; k <= n ; k ++) {
                    if(dist[i][k] == Integer.MAX_VALUE) continue;

                    if(dist[j][k] > dist[j][i] + dist[i][k]) {
                        dist[j][k] = dist[j][i] + dist[i][k];
                    }
                }
            }
        }

        for(int i = 1 ; i <= n ; i ++) {
            for(int j = 1 ; j <= n ; j ++) {
                if(dist[i][j] == Integer.MAX_VALUE) {
                    System.out.print(0 + " ");
                } else {
                    System.out.print(dist[i][j] + " ");
                }
            }
            System.out.println();
        }
    }
}