BOJ 11404 플로이드 Floyd-Warshall

다익스트라에 이어서 플로이드 워셜 알고리즘을 공부했다.

다익스트라를 모든 정점에서 돌리면 플로이드 워셜이 된다.

그런데 다익스트라는 음수 가중치를 가지는 간선이 있으면 안된다 한다.

플로이드 워셜은 모든 정점을 돌아보기 때문에 시간복잡도가 O(V^3)이다.

입력에서 중복값 확인을 해주니 정답이 됐다.

위키백과에 JAVA코드도 추가했다.

	import java.io.*;
	import java.util.*;
	/**
	* BOJ 11404 플로이드
	*/
	public class Main{
	private static final int MOD = (int)(1e+9)+7;
	public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int V = Integer.parseInt(br.readLine());
	int E = Integer.parseInt(br.readLine());
	int d[][] = new int[V + 1][V + 1];
	for(int i = 1; i<=V; i++){
	Arrays.fill(d[i], Integer.MAX_VALUE);
	d[i][i] = 0;
	}
	for (int i = 0; i<E; i++){
	String str1[] = br.readLine().split(" ");
	int a = Integer.parseInt(str1[0]);
	int b = Integer.parseInt(str1[1]);
	int c = Integer.parseInt(str1[2]);
	d[a][b] = Math.min(c, d[a][b]);
	}
	floyd(d, V);
	for(int i = 1; i<=V; i++){
	for(int j = 1; j<=V; j++){
	bw.write(d[i][j] + " ");
	}
	bw.write("\n");
	}
	bw.flush();
	}
	private static void floyd(int d[][], int V){
	for (int k = 1; k <= V; k++)
	for (int i = 1; i <= V; i++)
	for (int j = 1; j <= V; j++) {
	if (d[i][k] == Integer.MAX_VALUE || d[k][j] == Integer.MAX_VALUE) continue;
	if (d[i][j] > d[i][k] + d[k][j]){
	d[i][j] = d[i][k] + d[k][j];
	}
	}
	}
	}

view raw Floyd-Warshall.java hosted with ❤ by GitHub

위키백과 JAVA