When on a road trip, you might be eager to get to your destination as quickly as possible. In your home town, you're familiar with where the traffic gets bad at what time of day. However, on the road and in new places, you're lost without a hope on your own to be able to find the fastest route possible right away. Now imagine a program existed that was up to date on what the traffic was like and was able to navigate you through the worst of it, allowing you to get to your destination in a split no matter how unfamiliar you are with the area. In a nutshell, the program just described is an average GPS app, and it is likely using Dijkstra's Algorithm under the hood to find the shortest route possible, even factoring in the traffic!

Assumptions

  • Knowledge of Big-O notation
  • Proficiency with Breadth-First Search
  • Familiarity with Priority Queues and Heaps

What is Dijkstra's Algorithm?

Dijkstra's Algorithm is a graph searching algorithm that finds the shortest path from one node to all the other nodes in a graph, typically on a weighted graph using a BFS-like strategy and a priority queue.

It should be acknowledged that Dijkstra's Algorithm does not necessarily need to be implemented with a priority queue, however it is the most commonly implemented version of the algorithm.

> <a href="https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf" style="color:inherit;" target="_blank">This paper</a> excellently outlines alternative solutions and their respective performance.

 /* pseudo-code */
 // Two arrays to track distance and previous node.
 int[] distance, parent;

 function dijkstra( Graph G, int startVert ) {

   distance, parent = new int[ G.size ];
   // Set up a priority queue.
   PriorityQueue pq = new PriorityQueue();

   // Initialize the arrays.
   distance[ startVert ] = 0;
   for ( int vert in G.size ) {
     if ( vert != startVert ) { 
       // set each distance to infinity.
       distance[ vert ] = INFINITY;
     }
     // Signify it is unset with -1.
     parent[ vert ] = -1;
     // Add it to the queue
     pq.add( vert, dist[ vert ] );
   }

   while ( pq is not empty ) {
     int vert = pq.deleteMin();
     // Iterate over all adjacent vertices of vert. 
     for ( int adjV in G.adj[ vert ] ) {
       int tmp = distance[ vert ] + G.getEdgeLength( vert, adjV );
       // If the tmp path is shorter than the current.. 
       if( tmp &lt; distance[ adjV ] ) {
         // .. Set the distance and parent of adjV.
         distance[ adjV ] = tmp;
         parent[ adjV ] = vert;
         // Then update the priority queue.
         pq.decreaseKey( adjV, tmp );
       }
     }
   }

   // Most implementations might do this:
   return distance, parent;
   /* However, since they are global in this example
   it is not explicitly necessary. */
 }

Conceptualization

The algorithm works by starting at a selected vertex V, and taking note in a priority queue of the distances to all adjacent nodes. An additional array is tracked to maintain each node's parent node.

> The parent array is crucial for tracking the shortest path from vertex V to another vertex W.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Dijkstra_01.png" alt="before shortest path adjustment" style="width:600px;max-width:95%;">

</div>

Once all adjacent paths have been stored with the total distance from V and have been placed in the parent array, the priority queue is sifted down, and the first element is removed. This element is the current shortest path that exists in the explored portion of the graph.

Let's name the vertex taken out of the queue W. All adjacent nodes of this vertex are then looked at. Suppose vertex V shares a common neighbor with W called vertex U.

If the path from V to W to U is shorter than the path from V to U, the parent node of U is replaced with W and the new shortest distance to U is set.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Dijkstra_02.png" alt="after shortest-path adjustment" style="width:600px;max-width:95%;">

</div>

This procedure ensures that the current shortest path is always looked at next, which results in the shortest path to everywhere on the graph starting from V to be shown.

Performance Analysis

Performance Memory
O((V + E)LogV ) O(n)

Much like DFS and BFS, the running time of Dijkstra's Algorithm is dependent on the number of vertices and edges, which accounts for O(V + E).

However Dijkstra's Algorithm has an additional constraint in that most popular implementations use priority queues. On each iteration of the algorithm, after removing the top element from the priority queue, it needs to sift down the data to make sure that it maintains the rules of the min-heap.

This operation takes roughly O(log n) time. Given that we perform the sift down for each vertex that is seen, it fits the structure O(log V).

Combining the two results in a runtime performance of O((V + E) Log V).

Further Resources