728x90 최단경로1 [Algorithm] 다익스트라(dijkstra) 알고리즘 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지 최단 경로 다익스트라 알고리즘 : 음의 가중치 허용x 벨만-포드 알고리즘 : 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드 워샬 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함 탐욕 기법 사용, MST의 프림 알고리즘과 유사 def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -1 min_value = float('inf') for i in range(N+1): if not visit.. 2021. 10. 21. 이전 1 다음 728x90