플로이드-와샬1 [알고리즘 이론] 14. 최단거리 최단 거리 그래프 최단 거리 구하는 알고리즘이다. 1. 다익스트라 알고리즘 그래프의 최단 경로 구하는 알고리즘. 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함) 음수 가중치 없어야 함 인접 행렬로 표현된 그래프의 경우 시간 복잡도 : O(n^2) 우선순위 큐를 사용하여 시간 복잡도를 O(mlogn)까지 낮출 수 있다 -> 개선된 다익스트라 알고리즘 탐욕법과 동적 계획법 사용 원리 자세한 원리는 아래 게시글 참조 https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 알고.. 2023. 5. 9. 이전 1 다음