목록플로이드워셜 (1)

Seok_In

[알고리즘/Algorithm]최단경로(Shortest Path) (2)

저번 글에서는 다익스트라 알고리즘에 대해서 공부하였고, 이번 글에서는 이어서 플로이드 워셜에 대해 공부해보려고 한다. 🔷 플로이드 워셜 알고리즘 (Floyd=Warshall Algorithm) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우에 사용 할 수 있는 다익스트라 알고리즘과 달리 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 플로이드 워셜은 2차원 리스트에 최단거리 정보를저장하는 특징으로 N번의 단계를 수행하는데 단게마다 O(N^2)의 연산을 수행해서 총 시간 복잡도는 O(N^3)이다. 알고리즘은 노드의 개수가 N개 일 때 1번을 거쳐가는 경우 부터 N번째까지 거쳐가는 경우를 고려해서 그 중에서 사이사이..
Python/이것이 취업을 위한 코딩 테스트다 with 파이썬 2021. 8. 28. 22:01
이전 Prev 1 Next 다음