[Algorithm] 다익스트라 (dijkstra)

출처 - 위키백과

다익스트라 알고리즘

• 한 지점에서, 다른 모든 지점까지의 최단 경로를 찾는 알고리즘
• GPS, 라우팅 프로토콜 등에서 사용된다.
• A -> C 거리가 A -> B -> C 거리보다 짧다면 A에서 C까지의 최단 경로를 수정하는 방식이다.

---

heapq를 활용한 구현

• 1~2 : 모든 정점까지의 거리를 INF로 초기화 하고, 출발점(start) 자기 자신까지의 거리는 0으로 초기화한다.
• 3 : 거쳐가는 거리보다 바로 가는 거리가 짧다면 업데이트 하지 않는다.
• 4 : 거쳐가는 거리가 더 짧은 경우, 거리를 업데이트 한다.
• queue에 (거리, 도착 정점) 순으로 넣어야 거리가 짧은 정점부터 확인할 수 있다.

def dijkstra(start):
    distance = [int(1e9)] * (N+1) # 1
    distance[start] = 0 # 2
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, now = heapq.heappop(q)
        if distance[now] < cost: # 3
            continue
        for i in graph[now]:
            if cost + i[1] < distance[i[0]]:
                distance[i[0]] = cost + i[1] # 4
                heapq.heappush(q, (cost+i[1], i[0]))
    return distance