그래프 - 최단거리 알고리즘3 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘이란

다익스트라 알고리즘과 벨만 포드 알고리즘은 특정 시작 정점을 기준으로 다른 정점들까지 가는 최단 거리를 구할 때 사용하는 알고리즘이다.

플로이드 워셜 알고리즘은 모든 정점들간의 최단 거리를 구할 때 사용하는 알고리즘이다. 그 구현 방식은 세 알고리즘 중 가장 간단하게 느껴진다.

플로이드 워셜 알고리즘의 구현

플로이드 워셜 알고리즘의 구현은 경로를 하나씩 추가 시키면서 새로운 경로를 통해 갱신되는 최단 거리가 있으면 갱신해 주는 방식이다.
플로이드 워셜 알고리즘은 V^3의 시간 복잡도를 갖는다.

플로이드 워셜 알고리즘의 최적화

플로이드 워셜 알고리즘은 V^3의 공간 복잡도를 갖기 때문에 동적 계획법을 사용해서 메모리 사용량을 줄여줄 수 있다. 여기서 중복되고 불필요한 메모리 사용까지 줄이면 공간 복잡도는 V^2까지 줄일 수 있다.