최단거리

플로이드-워셜(Floyd-Warshall)? 플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다. 플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다. 또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다. 구현 설명 플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와..