[백준(Baekjoon)][자바(java)] 11404 : 플로이드 / 최단 경로

 

www.acmicpc.net/problem/11404

11404번: 플로이드

 

문제 풀이

 

-   방향 그래프의 플로이드 워샬( floyd-warshall ) 알고리즘 문제

 ☞  모든 정점 쌍 간의 최단 경로를 구함 ( 모든 쌍 최단 경로 문제 ).
       동적 계획법을 이용한, 벨만-포드 알고리즘의 연장선상에 있는 방법

-   인접 행렬로 그래프 표현

-   ( 배열의 0부터 사용하기 위해 정점 번호 입력받을 때 1씩 뺌 )

 

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

public class Main {
	
	static final int max = Integer.MAX_VALUE;
	
	public static long[][] floydWarshall( long d[][], int e[][], int n ) {
		int i, j, k;
		for( i = 0; i < n; i++ ) 
			for( j = 0; j < n; j++ )
				if( i != j )
					d[i][j] = e[i][j] == 0 ? max : e[i][j];
		for( k = 0; k < n; k++ ) {
			for( i = 0; i < n; i++ ) {
				for( j = 0; j < n; j++ ) {
					if( i == j ) continue;
					if( d[i][j] > d[i][k] + d[k][j] )
						d[i][j] = d[i][k] + d[k][j];
				}
			}
		}
		for( i = 0; i < n; i++ )
			for( j = 0; j < n; j++ )
				if( d[i][j] == max )
					d[i][j] = 0;
		return d;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		int n = Integer.parseInt( br.readLine() ),
			m = Integer.parseInt( br.readLine() ), i, j;
		int a[] = new int[3], e[][] = new int[n][n];
		long d[][] = new long[n][n];
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 3; j++ )
				a[j] = Integer.parseInt( st.nextToken() ) - 1;
			a[2]++;
			e[a[0]][a[1]] = e[a[0]][a[1]] > 0 ? Math.min( e[a[0]][a[1]], a[2] ) : a[2];
		}
		br.close();
		
		d = floydWarshall( d, e, n );
		
		StringBuilder sb = new StringBuilder();
		for( i = 0; i < n; i++ ) {
			for( j = 0; j < n; j++ )
				sb.append( d[i][j] + " " );
			sb.append("\n");
		}
		System.out.println( sb.toString() );
	}
}