[알고리즘] 최단 경로 알고리즘
최단 경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘 - 다익스트라 - 플로이드 워셜 - 벨만 포드 다익스트라 최단 경로 알고리즘 : 특정한 노드에서 다른 노드를 가는 최단 경로 - 음의 간선 X 1. 출발 노드 2. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 3. 최단 거리 테이블 갱신 4. 2, 3번 반복 구현 방법 1. 간단, 느린 방법 - 매번 최단 거리가 가장 짧은 노드 순회 + 테이블 갱신 2. 복잡, 빠른 방법 - 힙 이용 => 힙(Heap)을 이용해 우선순위 큐를 구현하고 이를 최단 거리가 가장 짧은 노드를 구하는 과정에 이용 heapq 라이브러리 -> 삽입과 삭제를 O(logN)에 수행 다익스트라 알고리즘 전체 시간 복잡도 = O(ElogV) 플로이드 워셜 알고리즘 :..
개발 공부 (알고리즘)
2021. 8. 22. 20:17
