[알고리즘] 플로이드 와샬 알고리즘(백준 11404)

플로이드 알고리즘은 그래프의 모든 꼭지점 사이의 최단거리를 구하는 알고리즘이다. 

- 음수 가중치를 갖는 간선도 순환만 없다면 처리할 수 있다. 

- 3개의 for문을 이용하여 처리한다. 

- 바깥 for 문은 중간지점, 가운데 for 문은 시작지점, 안쪽 for 문은 종료지점이다. 

	import java.util.Scanner;
	/**
	* 백준, 11404
	* 플로이드
	*
	* @author whitebeard-k
	*
	*/
	public class Problem11404 {
	static int N;
	static int M;
	static int[][] maps;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	M = sc.nextInt();
	maps = new int[N+1][N+1];
	for(int i = 0; i < M; i++) {
	int from = sc.nextInt();
	int to = sc.nextInt();
	int cost = sc.nextInt();
	// 거리중 최소값으로 입력
	if(maps[from][to] == 0) {
	maps[from][to] = cost;
	} else {
	maps[from][to] = Math.min(cost, maps[from][to]);
	}
	}
	sc.close();
	for(int mid = 1; mid <= N; mid++){
	for(int start = 1; start <= N; start++){
	if(maps[start][mid] == 0) // 연결이 안되면 처리 안함
	continue;
	for(int end = 1; end <= N; end++){
	if(maps[mid][end] == 0 || start == end)
	continue;
	// 중간 경로를 거쳐 가는 것이 그냥 가는것보다 빠르면 수정
	if(maps[start][end] == 0 || maps[start][end] > maps[start][mid] + maps[mid][end]) {
	maps[start][end] = maps[start][mid] + maps[mid][end];
	}
	}
	}
	}
	for(int x = 1; x <= N; x++){
	for(int y = 1; y <= N; y++) {
	System.out.printf("%d ", maps[x][y]);
	}
	System.out.println();
	}
	}
	}

view raw Problem11404.java hosted with ❤ by GitHub

플로이드 알고리즘 설명 

백준 11404 플로이드 - https://www.acmicpc.net/problem/11404