•
하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘인 다익스트라 알고리즘과는 다르게, 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최소값을 선택하여 다음 계산을 진행하는데 반해, 플로이드-워셜 알고리즘은 하나의 정점을 기준으로 모든 노드를 하나씩 다 거쳐가며 계산한다.
노드 1번부터 시작하여, x에서 y 정점으로 이동할 때 1번 노드를 거쳐가는 경우를 계산해주고, 그 이후 2번 노드를 거쳐가는 경우, 3번 노드를 거쳐가는 경우 … 와 같은 식으로 진행한다. 1번 노드를 거쳐가는 경우에는 x에서 y로 이동하는 비용과 x에서 1번 노드를 거쳐 y로 이동하는 비용을 비교하고 작은 값을 선택한다. 이 과정을 모든 노드를 진행하게 되면 모든 노드에서 모든 노드로 가는 최소값을 가진 이중 배열이 도출된다.