[백준] 플로이드 11404 - java

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

11404번: 플로이드

public class 플로이드11404 {
	final static int INF = 100001;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int map[][] = new int[n+1][n+1];
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == 0 && i!=j) {
					map[i][j] = INF;
				}
			}
		}
		
		
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			map[from][to] = Math.min(value, map[from][to]);
		}
		
		for(int k=1; k<=n; k++) {
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(map[i][j] > map[i][k] + map[k][j]) {
						map[i][j] = map[i][k] + map[k][j];
					}
				}
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(map[i][j] == INF) {
					System.out.print("0 ");
				}
				else {
					System.out.print(map[i][j]+" ");
				}
			}
			System.out.println();
		}
	}
}

플로이드 와샬 알고리즘은 모든 최단경로를 구하는 문제에 쓰입니다. 

특징으로는 음의 가중치를 갖고 있어도 사용할 수 있습니다.

시간 복잡도는 O(N^3)입니다. 

 

1. 인접행렬에 각 경로의 가중치 값을 입력받습니다.

2. 플로이드 와샬 알고리즘을 이용해 모든 경로에서 최단경로를 구합니다.

3. 결과를 출력합니다.