221115 플로이드워셜 알고리즘

위 그림처럼 간선에 가중치가 있고 최소 비용으로 각 정점에 도달하는 방법을 구할 때 사용함
DP(Dynamic Programming) 기법을 사용한 알고리즘으로 노드 0개를 거쳐가는 최단거리를 구하고, 노드 1개, 노드 2개...노드 N개를 거쳐가는 최단거리를 '단계적'으로 수행하며 기존 값보다 더 최단거리가 나오면 값을 갱신하는 방식

public static void floydWarshall() {
	// 경유노드 
	for(int k = 0; k < city; k++) {
		// 출발노드
		for(int i =0 ; i < city; i++) {
			// 도착노드
			for(int j = 0; j < city; j++) {
				//i에서 k를 거쳤다가 k에서 j 까지 가는 거리와 i에서 j 까지 가는 거리를 비교해서 작은 값이 최소거리이다.
				dis[i][j] = Math.min(dis[i][k] + dis[k][j], dis[i][j]);
			}
		}
	}
}

출처 : https://born2bedeveloper.tistory.com/44?category=1038707