다익스트라 파이썬 (1) 썸네일형 리스트형 파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, .. 이전 1 다음
