BOJ- 11404 ) 플로이드

---

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

11404번: 플로이드

---

플로이드-워셜문제의 기본적인 형태이다.

 

그래프에서 전체의 최단경로를 구할때에 O(N^3)으로 구할수있다.

 

For문을 돌면서 나와 인접하게 갈수있는 경로를 갱신하면서 최단경로를 구하는 알고리즘이다.

 

약간 외워서 푸는꼴.. 3중 for에 mid start end 순으로 들어가서 거쳐서 건너간다 라는 식으로 생각하면 쉽다.

---

import java.util.Scanner;

public class Main {
	static int num;
	static int INF = 2147000000;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		num = scan.nextInt();
		int graph[][] = new int[num+1][num+1];
		int bus = scan.nextInt();

		for(int y = 1 ; y <= num ; y++) {
			for(int x = 1 ; x <= num ; x++) {
				graph[y][x] = INF;
				if(y==x) graph[y][x] = 0;
			}
		}
	
		for(int index = 0 ; index < bus; index++) {
			int start , end  , cost ;
			start = scan.nextInt();
			end = scan.nextInt();
			cost = scan.nextInt();
			if(graph[start][end] > cost) graph[start][end] = cost;
			
		}
		
		
	
		
		for(int mid = 1;  mid<= num ;  mid++) {
			for(int start = 1 ; start <= num ; start++) {
				for(int end = 1 ; end <= num ; end ++) {
					if(graph[end][mid] != INF && graph[mid][start] != INF) {
						if(graph[end][start] > graph[end][mid] + graph[mid][start]){
							graph[end][start] = graph[end][mid] + graph[mid][start];
						}
					}
				}
			}
		}
		for(int y = 1 ; y <= num ; y++) {
			for(int x = 1 ; x <= num ; x++) {
				if(graph[y][x] == INF) System.out.print(0+" ");
				else System.out.print(graph[y][x]+ " ");
			}
			System.out.println();
		}
		
	}

}

---