Dijkstra's Algorithm

Shortest Path Finder

By: Allison Chou, Sasha Klezovich, Anita Leung, Sarah Zhou

Dijkstra’s Algorithm is an algorithm for finding the shortest path between two nodes in a graph. We can use it to model such things as road networks. It was created by a computer scientist by the name of Edsger W. Dijkstra in 1956 while working at the Mathematical Center in Amsterdam as a programmer to demonstrate the capabilities of a new computer called ARMAC. He designed the shortest path algorithm and later implemented it for ARMAC for a simplified map of 64 cities in the Netherlands. Dijkstra published his algorithm in 1959, two years after Prim and 29 years after Jarnik.

The original algorithm found the shortest path between two nodes and did not use a min-priority queue. Its runtime is proportional to |V|2 where |V| is the number of nodes. But a more common variant of this algorithm sets a single node as the “source” node and then finds the shortest paths from this node to all other nodes in the graph to produce a shortest-path tree. It also is based on a min-priority queue implemented by a Fibonacci heap and runs in |E| + |V|log(|V|) where |E| is the number of edges. An edge is represented as a path between two nodes. This updated method is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights. However, there are cases with bounded, or negative weights, directed acyclic graphs, among other conditions where specialized algorithms would be more efficient.

Walk Fast On Campus

You are a CSE student who lives in the CSE building. You wake up one morning on one of the couches in the breakout lounges and notice that you are late for class! What do you do? Your next class is in Bagley Hall, so you quickly use the showers in the CSE basement and then calculate which path from CSE to Bagley will take the least amount of time using Dijkstra’s algorithm. Since it is noon and prime time for classes, many paths around campus are congested, so the time it takes to travel most paths is longer than usual.

Your class in Bagley ran overtime! Now you are late for your next class in Mary Gates Hall. This day is certainly shaping up to be great. You perform Dijkstra’s algorithm again to find the most efficient path between Bagley and Mary Gates, and then hurriedly walk over to your next class.

One great usage of Dijkstra’s algorithm is to find the shortest path on a map. In the example to the right, we use a zoomed-in map of the University of Washington to display two different animations, one showing the process of finding the shortest-time path between the CSE building and Bagley, and the other showing the process of finding the shortest-time path between Bagley and Mary Gates. In addition to showing the process visually on the map, for each step the animations also show the change in the priority queue containing the next nodes to be explored.

Find Your Perfect Job

Here is another usage of Dijkstra’s algorithm. We have created a network with nodes representing individuals and the edges representing their skitchiness (lower numbers denote increased trust). We can see that there are multiple friend groups and companies.

Sarah wants a job at Google but doesn't know any Google recruiters. She wants to find the best path to consult a recruiter to secure herself the perfect job. She has multiple friends who know Google recruiters, in addition to other recruiters. If she goes through Mark, who has a fairly sketchy level of 1.3, so he is pretty trustworthy, she can rest easy knowing that he will connect her with his Google recruiter. However, the recruiter that he knows has a sketchy weight of 7.8, so is not very trustworthy. Examinging Sarah's other connections, we can see that her friend Allison, has a friend, Anita, who knows a Google recruiter. Getting to this recruiter requires more steps but in the end, everyone along the path is more trustworthy. Try clicking on a couple of people in the Google green bubbles. The individuals on the very ends represent the recruiters like Kacey and Sketchy McGee. Now, Sarah knows who to contact if she wants that job at Google.
The weight the appears under the graph shows the least amount of trust you need because a lower number indicates a more trustworthy path.

But what if Google isn’t the right company? After all, it’s safer to apply to more companies than not. Sarah isn’t going to take her chances only applying to Google. Most of her friends know other recruiters from companies like Facebook, denoted in Facebook blue, or Amazon, denoted in Amazon orange. Let’s view some of those companies to find the most trustworthy path to a recruiter. Now let’s view some of the sketchiest paths. We can see that even in some of the same companies we can have the more trustworthy or sketchy paths to interact with recruiters. Try clicking on Robyn. We can see that to get to Robyn we have to go through Patrick who has the worst trustworthiness. But, he also has the best connections to a recruiter. This path ends up being 10 for sketchiness while if we go to any other Amazon recruiters, Deanna or Jeff, their weights are greater. So, it actually pays off to go with the initially sketchy connection. This just goes to show that you need to make sure who you are networking with and to keep your options open when it comes to finding the perfect job and company for you.

We can also try to simulate some added distrust for fun, because afterall, trust can change. Suppose Allison and Anita got into a fight. Let’s simulate this by clicking on the edge between them. The edge wil thicken and the value will increase. This means that their trust has decreased. Now, if we try to see the best route to contact Kacey, with enough distrust between Allison and Anita, we could instead go through Toby.

Create Your Own Graph

Now, we will create our own graphs to model scenarios that we are interested in.

Dijkstra’s algorithm involves 5 steps:

  1. Add the nodes
  2. Add edges
  3. Select the starting and ending nodes
  4. Find the shortest path
  5. Shortest-path tree

Let’s explore each step in turn. We will assume we are computing shortest-path based on the repulsive weights between nodes.

Step 1: Adding Nodes.

The first thing that we need to do is to add nodes to our graph. For our purposes, a node represents a point of a graph. To add a node, simply click near the other nodes. Click the Next Step button if you want to go on to step 2. In that step, we will be adding edges between our nodes so we can later find the shortest path between the links in our graph.

You may add up to three additional nodes.

Step 2: Adding Edges.

The next thing that you need to do is add edges to our graph. These represent the physical links between the points in our overall graph. We have added a few for you. Currently, there are no weights between two nodes which means that crossing one edge is the same cost as another. This means that there is no immediate preference to travel from one node to its neighbors. You may add edges by dragging from one node to another. (Please keep in mind we intend to add some indication showing the drawn line when dragged in the future.)

Step 3: Select the starting and ending nodes.

The third thing that we need to do is determine which nodes we want to find the shortest path for. Please begin this step by clicking the node you want to start from. This node will appear lighter than the other nodes in the graph. Follow the prompts from the page notifications. Now, select the destination node by clicking on a node you want the path to from the lighter node. This destination node will appear as a darker color than the remaining nodes in the graph.

Step 4: Finding the shortest path.

This could potentially be the last step of algorithm, or arguably the whole algorithm in it of itself. The previous steps were focused on setting up the problem of finding the shortest path. Now, we will find the shortest path for the graph we have just created. To do this, we start with our lighter colored node. Our goal is to create a path from this node to the darker colored node. The first thing that we do is examine the nodes that neighbor the lighter node. We can also call these nodes the children of the start node.

One by one, we check if the children are the destination node. If one of them is the destination then we know that there is a path and this is a viable option. However, we would still have to continue checking our graph to ensure there is not a shorter path. If the child was not the destination node then we must mark this node as visited. This means that we have already seen this node before. We do this to track the current shortest path to this node. If we see this node again through a different path, then we check how many edges we had to traverse to see if this is the new shortest path to this node. We update the cost to travel to this node if a new path utilizes fewer edges.

We end up having a table with all of the nodes denoting the costs it takes to get to those nodes from the initial starting node. Once we cannot find smaller costs we can examine the total cost of the path and which nodes were used to reach the destination node from the starting node with the fewest edge traversals. This produces our shortest path.

Step 5: Shortest-path tree.

This step represents the finalized process of our graph showing the costs from the starting node to the ending node. After running Dijkstra through the previous steps, we can see that the numbers on the nodes have changed to reflect the cost from the start node to each of those nodes.

Johnson’s Algorithm

Dijkstra’s can be used as a subroutine for another algorithm such as Johnson’s Algorithm. Johnson’s algorithm is used to find the shortest path between all the pairs of vertices in a sparse, weighted, directed graph. Bellman-Ford algorithm is used to remove negative edge weights. First we add a new source node. Our formula is w(u,v)=w(u,v)+h(u)-h(u) where w(u,v) is edge weight, h(v) is the weight assinged to a single vertex, h(u) being the shortest possible distance. Removing the node, we now can run Dijkstra’s algorithm to find the shortest path on our new reweighted graph.

Conclusions

Dijkstra’s algorithm has a major impact for calculating the shortest distances between items in a model. This algorithm is wildly used in network routing protocols, and as a subroutine in other Algorithms such as Johnson’s.

Dijkstra’s algorithm is also known as uninformed-search and can be formulated as an instance of the general idea of best-first search.

This article was created using Idyll, with visualizations powered by D3 and Vega. The source code is available on GitHub.