1 플로이드 워셜 플로이드 워셜은 모든 정점 쌍 사이의 최단거리를 구하기 위한 방법이다. 음수 가중치인 간선이 있을 때에도 사용이 가능하지만 음수 가중치로 사이클이 만들어질 경우에는 사용할 수 없다. 구현은 다이나믹 프로그래밍을 이용하여 한다. 시간복잡도는 $O(N^3)$이다. 플로이드 워셜 알고리즘은 거쳐가는 정점을 기준으로 최단거리를 구한다. 먼저 1번 노드만을 거쳐간다고 할 때 모든 정점 쌍 사이의 거리를 구한다. 그 후에 1, 2번 노드를 거쳐갈 때도 구하고, 1, 2, 3번 노드를 거쳐갈 때도 구하는 것을 반복해서 모든 노드를 거쳐갈 때 최단거리를 구하게 되면 모든 정점 쌍 사이의 최단거리를 구할 수 있다. 2 예제바뀐 곳은 느낌표를 썼다. 초기상태0623inf60infinf32inf0in..
