플로이드-와샬 알고리즘이란? 다익스트라, 벨만포드 알고리즘과 더불어 대표적인 최단거리 찾기 알고리즘이다. 플로이드-와샬 알고리즘은 그 중에서도 모든 정점끼리의 최단거리를 한번에 계산할 때 사용한다. 즉, 다익스트라 알고리즘은 어떤 정점 A에서 다른 정점들까지의 최단거리를 계산한다면, 플로이드-와샬 알고리즘은 전체 정점에서 다른 정점들까지의 최단거리를 한번에 계산한다는 것이다. 다익스트라 알고리즘은 특정 정점을 중심으로 식을 계산시켜 나간다면, 플로이드-와샬 알고리즘은 계산을 위해 거쳐가는 정점을 중심으로 계산해나간다는 것이다. 또한, 플로이드-와샬 알고리즘의 중요한 특징 중 하나는 동적 계획법을 이용하여 최단 거리를 계산해나간다는 것이다. 동작 원리 위와 같은 초기 상황이 주어졌다고 가정하자. 일반적인 ..