플로이드-워셜 알고리즘 가중치 그래프에서 만들 수 있는 모든 두 정점 사이의 최단 거리를 구하는 알고리즘이다. 이 그래프를 사용하기 위해선 가중치가 음이 아니여야 한다.(음수이면 무한정으로 음수를 더함) 플로이드 워셜 알고리즘은 최단 거리를 구하기 위해 동적 프로그래밍 방식을 사용한다. 먼저 그래프에서 모든 노드로 가는 최단 거리를 2차원 배열로 만든다. 이때 자기 자신(1 -> 1)으로 가는 최단 거리는 0이다. 또한 갈수 없는 노드는 무한으로 표현한다. 프로그램에서는 무한대 표현이 불가능함으로 무한대를 나타낼 수 있는 충분히 큰 수로 대체한다. 2차원 배열을 모든 정점의 개수가 n개일 때 n * n형태의 배열이 만들어진다. 1 2 3 4 5 1 0 1 3 - - 2 1 0 4 7 - 3 3 4 0 -..
