[Algorithm] 플로이드-워셜

❓ 플로이드-워셜이란?

---

음수 사이클이 없는 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘

 

 

❓ 플로이드-워셜

---

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

public class Main { // 플로이드

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());
		int m = Integer.parseInt(bf.readLine());

		int arr[][] = new int[n][n];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.MAX_VALUE;
				if (i == j)
					arr[i][j] = 0;
			}
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			arr[a - 1][b - 1] = Math.min(arr[a - 1][b - 1], c);
		}

		// [시작 노드, 끝 노드] = [시작 노드, 중간 노드] + [중간 노드, 끝 노드]
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					if (arr[j][i] == Integer.MAX_VALUE || arr[i][k] == Integer.MAX_VALUE)
						continue;

					arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
				}
			}
		}
	}
}