Dijkstra’s algorithm¬†computes the shortest distance between two vertices in a graph. Vertices in a graph are connected by an edge with a positive length.

An extremely fast implementation for Heap which can be used in Dijkstra’s algorithm is shown below:

MinHeap implements two methods (at a minimum):

  1. Insert.
  2. Extract Min.

For Dijkstra’s algorithm, it is required to update the edge length from the middle of the heap. The above post has additional methods for a Min Heap to implement the update and delete operations.

Dijkstra’s algorithm is used to compute the All Pair Shortest Path problem (via the Johnson’s reweighting technique). Even for relatively dense graphs, Dijkstra’s algorithm is faster than the more general Floyd Warshall’s algorithm.

For a graph with 1000 vertices and 45,000 edges (m = n^1.63), the Floyd Warshall’s algorithm completed the computation in 6 seconds. Dijkstra’s algorithm computed¬†in 3 seconds. For a graph with 20,000 vertices and nearly 1,000,000 edges (m = n^1.45), the Floyd Warshall’s algorithm computed in 7 hours, whereas Dijkstra’s algorithm computed under 20 minutes.

Clearly, Dijkstra’s algorithm with the Johnson reweights is a better solution than Floyd Warshall’s algorithm¬†with a good Min Heap implementation.

Min Heap implementation for Dijkstra algorithm
Tagged on:

Leave a Reply

Your email address will not be published. Required fields are marked *