[알고리즘] 플로이드 워셜(Floyd-Warshall)

목 차플로이드 워셜(Floyd-Warshall)기본 개념과 작동 원리구현하며 배운 것들구현 방법 플로이드 워셜(Floyd-Warshall) 최단 경로를 구하는 알고리즘 중에는 대표적으로 다익스트라 알고리즘이 존재한다. 다익스트라 알고리즘의 경우 한 점에서 다른 한 점으로의 최단경로를 구하는 반면에 플로이드 워셜은 모든 정점 사이의 최단경로를 찾는 데에 사용된다. 시간 복잡도는 O(V^3)이다. 기본 개념 및 작동 원리 기본 개념위에서 언급하였듯이 모든 정점의 최단경로를 찾는 알고리즘이다. 작동 원리기본적으로 동적 프로그래밍을 기반으로 작동을 하지만 복잡하면 굳이 생각하지 않아도 된다. 이 알고리즘에서는. 이 알고리즘에서는 각 점을 순회하는데, 시작점으로써가 아닌 '경유점'의 개념으로 접근을 하게 된다. ..

Algorithm 2024.02.06