[Algorithm] 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘

 

: 시작 노드에서 도착 노드로 갈때 특정 노드를 거쳐가는것이 더 빠르다면 최소값을 갱신해 주는 알고리즘

 

 

플로이드 워셜 알고리즘에는 다이나믹 프로그래밍이 녹아들어 있습니다. 두 알고리즘 모두 문제를 해결할때 점화식을 사용하기 때문입니다.

 

점화식은 다음과 같습니다.

 

D_ab = min(D_ab, D_ak + D_kb)

a에서 b로 가는 값을 a에서 b로 가는 값과 a에서 k를 거쳐 b로 가는 값중 작은 값으로 갱신하라는 의미입니다.

 

플로이드 워셜 알고리즘은 이미 값을 가지고 있는 노드간의 거리에 특정 노드 k를 거쳐가는 과정을 수행해 줘야 하기에 3중 for을 사용합니다. 

 

그래서 시간 복잡도는 O(N³)이 됩니다.

 

다음은 플로이드 워셜 알고리즘의 최소값 갱신 과정입니다.

 

노드 사이의 관계

 

노드 사이의 거리 표로 구성

 

특정 노드를 1로 했을때의 최소값 갱신

 

특정 노드를 2로 했을때 최소값 갱신

 

특정 노드를 3으로 했을때 최소값 갱신

 

특정 노드를 4로 했을때 최소값 갱신

이렇게 최소값을 갱신해 줄 수 있습니다.

 

유튜버 나동빈님의 유튜브 채널에서 쉽게 설명을 해주셔서 링크를 첨부합니다.

https://www.youtube.com/watch?v=hw-SvAR3Zqg