Dijkstra's Shortest Path (Heap)

Dijkstra’s shortest path algorithm calculates the shortest distance between vertices in a weighted graph with non-negative edge weights. This is without a doubt one of the greatest hits of algorithms with countless applications. Those wishing to excel in computer science should take extra car to ensure they fully understand this.

By making a small change from the naive implementation to the way in which the vertex with the minimum distance is determined, it’s possible to reduce the running time of Dijkstra’s algorithm. The trick is to use a heap.

Asymptotic Complexity

$O((n + m)\log_2 n)$

Pseudo Code

G = input graph with distance of each vertex set to infinity
v = starting vertex
H = head using vertex.distance as the key
side effects: marks all vertices with the shortest distance from the starting
vertex

v.distance = 0
H.insert(v)

while H is not empty:
    u = H.extract_minimum

    for each outgoing edge in u:
        if edge.head has already been processed, skip it

        distance = u.distance + edge.weight
        if distance < edge.head.distance
            edge.head.distance = distance

            if edge.head exists in H:
                // Force reorder of keys
                H.delete(edge.head)
                H.insert(edge.head)
            else
                H.insert(v)

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions