플로이드

모든 노드 정점간의 최단거리를 구하기 위한 알고리즘 각 노드에서 바로 갈수 있는 정점을 먼저 배열에 표시

노드에서 거쳐가는 노드를 확인한다

• 배열 가장 왼쪽부터 위에서 아래로 확인을 지금 확인한 노드가 특정정점으로 간다면
  특정 정점으로 가는것을 확인하고 그 특정 정점을 거쳐서 갈수 있는 최단거리를
  지금 노드를 기준으로 비교하고 업데이트

배열을 사용하기 때문에 공간복잡도 문제 음수에서도 사용 할 수 있다

package Jun_2020_05_11;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[][] di;
	static int[][] p;
	static int n;
	static ArrayList<Node>[] list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		int m = sc.nextInt();

		di = new int[n + 1][n + 1];
		p = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				di[i][j] = 10000000;
			}
			di[i][i] = 0;
		}

		for (int i = 0; i < m; i++) {
			int s = sc.nextInt();
			int f = sc.nextInt();
			int cost = sc.nextInt();
			if (di[s][f] > cost)
				di[s][f] = cost;
		}

		floyd();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (di[i][j] == 10000000)
					di[i][j] = 0;
				System.out.print(di[i][j] + " ");
			}
			System.out.println();
		}

	}
/////////////////////////////////////////////////// 알고리즘 구현 부분
	static void floyd() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (di[j][i] != 0 && di[j][i] != 10000000) {
					for (int k = 1; k <= n; k++) {
						if (di[i][k] + di[j][i] < di[j][k])
							di[j][k] = di[i][k] + di[j][i];
					}
				}
			}
		}
	}
////////////////////////////////////////////////////
	static class Node {
		int f, cost;

		Node(int f, int cost) {
			this.f = f;
			this.cost = cost;
		}
	}
}