플로이드 - 워샬 알고리즘

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

[모든] 정점과 정점 사이의 최단 거리를 알고 싶을 때 사용

(시간 복잡도 O(N^3)으로 그렇게 성능이 좋지 않다) 

11404번: 플로이드

import java.io.*;
import java.util.*;

public class  Main {

    private static int n,m;

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static long weight[][];

    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{

    n = Integer.parseInt(br.readLine());
    m = Integer.parseInt(br.readLine());

    weight = new long[n+1][n+1];
    for(int row = 1; row <= n;row++){

        for(int column = 1; column <= n;column++){

            if(row == column ) continue;

            weight[row][column] = INF;
        }
    }

    for(int x =0 ;x < m;x++){

        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

        weight[a][b] = Math.min(weight[a][b],w);
    }

    floyd();

    for(int row = 1;row <= n;row++){

        for(int column = 1;column <= n;column++) {

            if(weight[row][column] == INF)
                System.out.print(0 +" ");
            else
             System.out.print(weight[row][column] + " ");
        }
        System.out.println();
    }

    }

    static void floyd(){

        for(int x = 1; x <= n; x++){

            for(int row = 1; row <= n; row++){

                for(int column = 1;column <= n;column++){

                    if(weight[row][column] > weight[row][x] + weight[x][column])
                        weight[row][column] = weight[row][x] + weight[x][column];

                }
            }
        }
    } // floyd
}