다익스트라
-
[Python]다익스트라 알고리즘 구현(Dijkstra algorithm)프로그래밍/알고리즘 2022. 9. 20. 16:47
이번 글에서는 파이썬 언어를 사용하여 다익스트라 알고리즘을 구현합니다. 1. 다익스트라 알고리즘이란? 노드(node)간에 방향과 가중치를 가지는 간선(edge)으로 연결된 그래프에서, A지점에서 B지점으로 가는 최단거리를 구할 수 있는 알고리즘. 단, 간선의 가중치가 양수일 경우에만 사용 가능하다. 2. 구현 코드 우선순위 큐 준비 import heapq 그래프 인접 리스트 준비 node_n = 6 # (출발노드,도착노드,이동값) arr = [(0,1,7),(1,2,3),(2,0,1),(0,3,4),(2,3,5),(3,2,1),(3,4,8),(4,3,1),(2,4,2),(1,4,4),(4,5,2),(3,5,9)] adj_lst = [[] for x in range(6)] for sp, ep, cost i..