[알고리즘] 백준 > #11404. 플로이드

문제링크

백준 #11404. 플로이드

풀이방법

문제이름에서도 알 수 있듯, 플로이드 와샬 연습문제입니다. 플로이드 와살 알고리즘이란, V개의 정점과 거리가 주어졌을 때, 모든 정점 쌍 사이의 거리를 계산하는 알고리즘입니다!

플로이드 와샬 알고리즘은 dp를 기반으로 구현할 수 있습니다. 최단경로 탐색 시 사용하는 정점을 1번 노드, 1번 + 2번 노드, ..., 1번 + ... + N번 노드 이렇게 늘려가는 방식이에요! 노드를 점차 늘려가며 k번 정점을 우회하면 더 짧아지는 지 확인하면 됩니다~ 따라서, 시간복잡도는 O(V^3) 입니다.

!!) 다익스트라를 사용하면 안되나요?
됩니다. 다익스트라 알고리즘은 모든 정점에 대해 돌렸을 때, O(V(E + VlogV))의 시간복잡도를 갖게 됩니다. 따라서, E <<< V^2 일 때는 다익스트라가 유리하겠네요. 단, 음의 가중치를 가질수 있는 경우엔 불가능합니다~

코드

import java.util.Scanner;

public class Floyd {
    static final int NOT_VISITED = 100000000;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int dist[][] = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) dist[i][j] = NOT_VISITED;
            dist[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            int nodeA = sc.nextInt();
            int nodeB = sc.nextInt();
            int cost = sc.nextInt();

            if (dist[nodeA][nodeB] > cost) dist[nodeA][nodeB] = cost;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) result.append((dist[i][j] != NOT_VISITED ? dist[i][j] : 0) + " ");
            result.append("\n");
        }

        System.out.print(result.toString());
    }
}