Dijkstra's Algorithm

Get home for Christmas! 🎄🎁✈️

Picture this: it’s the holiday season, and you’re taking in the sights and sounds of beautiful New York, New York. But being the forgetful freshman that you are, you happened to forget that Christmas day is the day right after tomorrow! You panic for a moment, but soon realize that you can just book a direct flight home to Seattle. However, it looks like all the direct flights have already been booked, and you realize that you’ll have to instead take a series of connecting flights if you want to make it home in time. Let’s try to find the cheapest route you can take from JFK to SEA! On the map below, paths have been drawn between connected airports. Each path is labeled with the cost of the flight (so from SEA to LAX, it would cost $175). What’s the cheapest way to get from JFK to SEA?

Great, you found the cheapest way back and made it home in time for the holidays! However flights aren’t usually as sparse as above, and there are usually many more paths to consider when trying to get from point A to point B. Take a look at the map below, which is a more accurate representation of the flights available. If you were to use your method from the map above, how hard would it be to find the cheapest path home? Luckily there’s an algorithm called Dijkstra’s Algorithm which helps us do that.

Click on an initial node (outlined in black) and a destination node (outlined in gray), and press run on the map below to watch the algorithm find the cheapest path home. Then, continue on to learn about how the algorithm works!

Introduction

Dijkstra’s algorithm was created by Edsger W. Dijkstra in 1956. There are many variants of this algorithm. Dijkstra’s original found the shortest path between two nodes. A more common variation finds the shortest path from the source to all other nodes, creating a shortest-path tree (this is what we show below).

Step-by-Step

Implementations & Run Time

The run time of this algorithm can be affected by using different data structures to store and access the nodes. For any implementation, the run time is where denotes the number of edges, the number of vertices, the complexity of the decrease key operation, and the complexity of the extract minimum operation. The decrease key operation is only used in heap implementations. Extract minimum is the operation used to find the next closest vertex.

Source

Array

The simplest implementation uses an ordinary linked list or array. Finding the minimum distance node is really simple. It’s just a linear search through all the nodes!

The visualization on the right shows how we traverse through the array and continually update the minimum.

Because there is no decrease key when we use arrays, and extracting the minimum goes through each vertix once, the run time is time is .

Binary/Binomial Min-Heap

Source

A heap is a tree-based data structure that that can either be used to keep track of the minimum or maximum value in a set of numbers. For Dijkstra’s Algorithm, because we want to choose our next node to explore based on the distance from the original node, we want to keep track of the minimum distance, so we would be using a min-heap. The root node, which is the top most node, keeps track of the minimum value. The min-heap has to satisfy two properties to maintain it’s min-heap status:

1. Each parent node has to be less than or equal to its child nodes.
2. All levels of the tree have to be fully filled, and if the last level of the tree is not filled, they are filled from left to right.

As new values are added, nodes will switch places to maintain this property, as shown on the right.

So when selecting the next node to visit, all we need to do is take the node that’s stored at the root of the tree. A binomial tree is just like a binary tree, except in a binary heap, the heap is a single tree. In a binomial heap, the heap is a collection of smaller trees, where each tree is also a binomial tree. Ben Frederickson has a really insightful visualization of a heap on his website here.

Using a self balancing binary heap, the decrease key and extract minimum operation both take log|V|. Thus, the algorithm requires in the worst case.

Fibonacci Heap

It only starts to do work once we remove the min.

Source

The University of San Francisco has a really helpful visualization here.

Because it defers most of its work until something is removed, adding nodes and accessing the minimum take constant time. The only thing that takes more time to compute is the extract minimum, which takes log|V|, so the total run time is

Limitations Of Dijkstra’s Algorithm

Negative Edge Weights

For the example on the right, let’s say we want to get from A to B. We start at node A and evaluate both edges. The edge to B is 1 and the edge to C is 2. Since the edge to B is shorter, we take that path and change our current node to B. Now that we’ve ended up at our destination node we stop the algorithm. The algorithm, however, hasn’t discovered the actual shortest path. The path from A to C to B is the shortest, with a weight of -1. If we wanted to find a path in a graph with negative edges, we would have to use a different algorithm. The Bellman-Ford algorithm is able to handle graphs with negative edges as long as there aren’t negative cycles. Read more about it here!

Unreachable Nodes

Let’s imagine that we have a node A that is not connected to any other node in the graph. Since all nodes are initially set to a tentative distance of infinity, node A will always retain a tentative distance of infinity because it cannot be reached.