개요 플로이드-와샬 알고리즘은 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 가중치가 음인 그래프는 있지만, 음수 싸이클은 없다. (음수 싸이클이란? 음의 가중치가 더 커서 최단 경로를 계속해서 줄일 수 있는 상태의 간선을 말함.) 벨만-포드와 음의 가중치의 최단 경로를 계산할 수 있다는 점에서 비슷하지만, 플로이드-와샬 알고리즘은 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 즉, 벨만-포드와 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로의 최단 경로를 구했다면, 플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구한다. 또한 플로이드-와샬 알고리즘은 다이나믹 프로그래밍으로 볼 수도 있다. 알고리즘 알고리즘 분류..