Dijkstra algorithm
-
다익스트라(Dijkstra) 알고리즘Programming/python 2021. 3. 10. 09:51
특정 정점까지 가는데 최소 비용을 찾는 알고리즘이다. 실생활에서 네비게이션에서 빠른길 찾기의 개념과 유사하다. 시작점이 주어지고, 특정 정점까지 오는데 가중치를 최소비용으로 계산하면 된다. distances에 각 정점에 도착하는 최소비용을 저장, 나중에 특정 정점을 꺼내오면 된다. distances는 구현하기 나름이긴한데, 정점이 영문이면 dictionary를 사용하고 숫자면 list를 쓰면 된다. 물론 둘다 dictionary를 사용하기도 한다. 그리고 다익스트라는 힙을 사용해서 구현한다. (python에서는 heapq모듈을 사용하는데, 최소 비용으로 자동 정렬되기 때문이다. 처음에 distances(각 정점에 도달하는 비용)은 무한대로 잡아놓고, 출발점만 0으로 잡는다. 이렇게 하는 이유는 얼마가 최..