플로이드 워셜 알고리즘

플로이드 워셜 알고리즘은 최단 경로를 구하는 알고리즘 중에 하나로,

일반적으로 다익스트라 알고리즘과 같이 양수 가중치를 가진

그래프에서 사용할 수 있는 알고리즘이다.

플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다르게

모든 노드에 대하여 모든 노드에게로 가는

최단 경로를 구할 수 있는 알고리즘이다.

플로이드 워셜 알고리즘의 작동 방식은 다음과 같다.

매번 특정한 노드 $k$를 거쳐가는 것이 더 짧다면 최단경로를

그 경로로 갱신해준다.

이미지 출처: 이코테