Dijkstra's Algorithm

Dijkstra repeatedly takes the unvisited vertex with the smallest known distance (using a priority queue) and relaxes its edges:

$d[v] = \min(d[v],\ d[u] + w(u, v))$

import heapq
def dijkstra(graph, src):
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Complexity $O((V + E)\log V)$. It fails with negative weights — use Bellman-Ford for those.