[백준]플로이드(11404)

• 플로이드-워셜 알고리즘이다.
• 어떤 두 정점 사이의 최단 경로는 어떤 경유지 K를 거치거나 거치지 않는 경로 중 하나이다. 즉, 정점 A와 정점 B 사이의 최단 경로는 A-B 이거나 A-K-B이다.
• 만약 경유지 K를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로이다. 다시 말해, 만약 A-B의 최단경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로이다.
• 특징
  • 순환만 없다면 음수 가중치도 가능하다.
  • 기본적으로 동적계획법으로 접근한다.
  • 모든 가능한 경유지에 대해서 모든 정점에서 모든 정점으로 가는 최단거리를 확인하므로 연산횟수는 V^3이고, 따라서 시간복잡도는 O(V^3)이다.

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

public class Main {
    public static int n;
    public static int[][] distance;
    public static final int INF = 1000000000;

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

        n = Integer.valueOf(br.readLine());
        int busCount = Integer.valueOf(br.readLine());

        distance = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                distance[i][j] = INF;
            }
        }

        while (busCount-- > 0) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.valueOf(st.nextToken());
            int end = Integer.valueOf(st.nextToken());
            int time = Integer.valueOf(st.nextToken());

            distance[start][end] = Math.min(distance[start][end], time);
        }

        // 프로이드-워셜
        for (int k = 1; k <= n; k++) {          // 경유지가 K라면
            for (int i = 1; i <= n; i++) {      // 시작점
                for (int j = 1; j <= n; j++) {  // 도착점
                    distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]);
                    // A-K-B와 A-B를 비교해서 짧은 거리를 저장
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (distance[i][j] >= INF)
                    sb.append("0 ");
                else
                    sb.append(distance[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}