플로이드-워셜

플로이드-워셜

플로이드-워셜 알고리즘은 음의 사이클이 없는 그래프에서 모든 정점에서 모든 정점까지의 최단 거리를 모두 구할 수 있는 알고리즘이다.

플로이드-워셜 알고리즘은 다이나믹 프로그래밍을 사용하여 각 노드간의 최단거리를 계산한다.

O(V^3)의 시간복잡도를 갖는다.

플로이드-워셜 구현

거리 배열을 inf(최댓값)으로 초기화한다.

출발지점과 도착지점이 같으면 최단거리가 0이므로 0으로 채운다.

3중 반복문을 이용해 모든 경로를 체크해 최단거리를 구한다.

j -> k 의 최단 거리를 구할 때 1 ~ n 모든 지점을 경유해 가는 경로를 보고 최단 거리를 구한다.

import java.util.*;
import java.io.*;

public class Main {
	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 n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		int[][] d = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(d[i], 1000000000);
			d[i][i] = 0;
		}

		while (m-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			d[a][b] = Math.min(d[a][b], c);
			d[b][a] = Math.min(d[b][a], c);
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				for (int k = 1; k <= n; k++)
					d[j][k] = Math.min(d[j][k], d[j][i] + d[i][k]);
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][j] == 1000000000)
					bw.write("INF ");
				else
					bw.write(d[i][j] + " ");
			}
			bw.write("\n");
		}
		bw.flush();
		bw.close();
	}
}