Dijkstra Code

Dijkstra’s algorithm is a method to calculate the shortest path from one node to another with weighted edges. It does not work for negative edge weights, however.

Fun fact: it is a main algorithm used in Google Maps.

It starts off by setting all the distances of each node to infinity. Then, as it traverses, it updates the nodes with the new shortest paths, and it keeps going until the end node is reached.

Code implementation in python (uses priority queue, not array):

import heapq

def dijkstra(g, s):
    """
    g: Dict representing the graph (as an adj lst). 
       Keys are nodes, values are lists of (neighbor, weight) pairs.
    s: Start node.

    Variables:
    d -> Dictionary storing shortest distances from s to each node.
    pq -> priority queue for processing nodes
    v -> Set to track visited nodes.
    """
    d = {n: float('inf') for n in g}
    d[s] = 0
    pq = [(0, s)]
    v = set()
    while pq:
        c, n = heapq.heappop(pq)
        if n in v:
            continue
        v.add(n)

        for nb, w in g[n]:
            if nb not in v and c + w < d[nb]:
                d[nb] = c + w
                heapq.heappush(pq, (d[nb], nb))
    return d

Time complexity is O((V+E)logV)