다익스트라는 그리디와 DP의 유형으로 분류되는 최단경로 알고리즘이다. DP는 계속해서 그래프를 갱신하기 때문이고 그리디는 그 순간 가장 짧은 정점을 선택하기 때문이다. 음의 가중치가 적용될 수 없어 일상생활 문제에서 잘 사용될 수 있다. 특정한 한 노드에서 다른 모든 노드로 가는 최단 경로를 찾는 알고리즘이다. 원래는 O(V^2)의 시간복잡도를 가진다. ( 리스트 이용, 돌면서 가장 거리가 짧은 노드를 찾는 경우) 이것은 5,000개 까지는 괜찮지만 개수가 10,000개가 되면 시간초과가 될 가능성이 농후하다. (파이썬은 1초에 2천만 연산이라고 생각하면 됨) 시간초과를 막기 위해서 heap을 이용하면 된다. (방문하지 않은 최단거리의 정점을 찾을 때 이용) 파이썬의 minheap은 heappop을 하면..