(알고리즘) Floyd 워셔 알고리즘

복잡도
플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 O(|V|^3) 시간 복잡도를 갖는다. 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 O(|V|)의 시간 복잡도를 갖는다. 종종 다익스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.

댓글

이 블로그의 인기 게시물

(ElasticSearch) 결과에서 순서 정렬

(네트워크)폴링방식 vs 롱 폴링방식

(18장) WebSocekt과 STOMP를 사용하여 메시징하기