다익스트라 (2) 썸네일형 리스트형 파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, .. 백준 1912번: 최소비용 구하기 파이썬 코드(다익스트라) import heapq import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) INF = sys.maxsize graph = {} dist = [INF] * (n) queue = [] for _ in range(m): s,t,w = map(int, sys.stdin.readline().split()) if s-1 not in graph: graph[s-1] = [[t-1,w]] else: graph[s-1].append([t-1,w]) startpoint, endpoint = map(int, sys.stdin.readline().split()) def dijkstra(start): heapq.heappush(queue, [0, sta.. 이전 1 다음
