Floyd-warshall1 [파이썬] 최단 경로 찾기 알고리즘 [Algorithm #5] 각 노드 사이의 거리가 다르게 주어졌을 때, 최단 경로를 찾는 알고리즘에는 크게 다익스트라와 플로이드 워셜 알고리즘이 사용된다. # 다익스트라 알고리즘 : Dijkstra Algorithm 다익스트라는 시작 노드에서 출발하여, 거리가 가까운 노드부터 차례대로 방문하여 해당 노드를 거쳤을 때의 거리가 더 짧으면 최단 거리를 갱신하는 알고리즘이다. N개의 노드가 있다면 N개의 노드에 대해 N-1개의 노드를 확인해야 하므로 O(N^2)의 복잡도를 가진다. 하지만 heapq를 이용한 우선순위 큐를 쓰면 O(ElogN)까지 낮출 수 있다. (거리, 노드)로 구성된 튜플을 우선순위 큐에 넣는다. 이렇게 한 뒤, 주변 노드들을 살펴볼 때 Min Heap을 이용한 우선순위 큐를 이용하므로 거리가 가장 짧은 원소부터 p.. 2022. 8. 24. 이전 1 다음 728x90