[JAVA] 플로이드-워셜 알고리즘

플로이드-워셜 알고리즘 그래프에서, 한 정점에서 다른 정점으로 가는 최단거리가 있다. 플로이드-워셜 알고리즘을 사용한다면 각각의 모든 정점에서 모든 정점으로 가는 최단거리를 전부 구할 수 있다. 즉, 1 ~ 2, 1 ~ 3, 1 ~ N 2 ~ N 3 ~ N 4 ~ N 5 ~ N 모든 경로에서 전부 최단 거리를 구할 수 있다. 2 -> 1로 가는 최단 경로를 볼 때, 2 -> 1은 9 2 -> 3 -> 1은 7로 노드 3을 거쳐가는 것이 더 빠름 이렇게 노드를 거쳐서 가는게 더 빠른 경로까지도 플루이드-워셜 알고리즘을 통해 구할 수 있다는 것이다. 플로이드-워셜 알고리즘은 DP(Dynamic Programming) 기법을 사용한 알고리즘이다. 즉, 노드 0개를 거쳐가는 최단거리를 구하고, 노드 1개, 노드..

2022.03.19