Algorithm & Data Structure
2022. 11. 2.
플로이드 워셜(Floyd Warshall) 알고리즘
로봇공학을 공부하다가 알고리즘 파트가 나와서 공부해볼 겸 정리를 해본다. pdf에는 단순히 DP를 이용한 최단거리 탐색 이라고 적혀 있지만, 사실상 플로이드 워셜 알고리즘을 설명하고 있다. 최단 거리를 찾는 알고리즘의 일종이다. "거쳐가는 정점을 기준으로 최단거리를 구하는 것" DP를 이용한다. 이러한 그래프의 방문의 최적 비용을 2차원 테이블로 표현해 보자. 이는 현재까지 계산된 최소비용이다. 2열 3행은 2-> 3으로 가는 현재까지 계산된 최소비용이고, 이는 9이다. 무한으로 표시된 것은 한 번의 이동으로는 갈 수 없는 즉, 필연적으로 다른 노드를 거쳐야 하는 경우이다.(만약 연결된 노드가 없는 경우 못 갈 수도 있다.) 예를 들어 1->3으로 가는 경우는 1 -> 4 -> 3을 거쳐서 비용 11, ..
