Food for Thought: An Introduction to Dijkstra's Algorithm Using Food Delivery
Penny King & Garvey Li

We turned the map into a simple graph using circles and lines. The restaurant you are currently at is the blue dot at the left.

The pink dots are neighborhoods you can pass through on your drive.

The numbers represent how many minutes it takes to get from one neighborhood to another. And the lines are one-way roads that link different neighborhoods to each other.

This red dot is your final destination.

Try to find the fastest path possible to your destination. Create the path you think is best by clicking on the nodes. Scroll down when you are done!

Was this what you got?

Finding the shortest path is not a simple task… In fact, it can be quite tricky especially in even bigger maps to find the fastest path to the customer. How can we find the concrete shortest path to your customer in an efficient manner?

One method to do so in this situation is called Dijkstra's Algorithm

Dijkstra's Algorithm is very similar to the Breadth First Search algorithm, and lets us find the shortest path between a source and target node on a positively weighted graph (directed or undirected). In our explanation "u" describes any node (circle) in our map.

To start out, we define an estimated distance value– u.est for each node u. This denotes a node's estimated distance from the source node.

We already know it takes 0 minutes to get to the source node a), so a.est = 0. However, for all other neighborhoods and the final destination, we do not know the fastest time it will take yet. Therefore u.est is unknown for all other nodes, so we set them to positive infinity.

To help us keep track of which nodes to update and which edges to look at, we'll categorize the nodes into two groups: Visited and Unvisited.

Nodes in Visited have a known shortest distance from the source node, while nodes in Unvisited do not.

With the setup done, we're ready to start!

The first step is to look at all the nodes in Unvisited that are 1 edge (road) away from (or adjacent to) the Visited nodes.

In the context of our map, we want to see the neighborhoods that are the closet to us by road.

In this case, those nodes are f, b, and c.

Then, we calculate new distance values for each of the Unvisited nodes adjacent to the Visited nodes.

We do this by adding the edge weight (time to travel down the road) to the u.est value of the connected Visited node.

If the new distance value is less than the respective Unvisited node’s u.est, then we update u.est to be the calculated distance value.

For node f, infinity > 0 + 7, so f.est is now 7.

Now, the next step is to find a node with the shortest estimated path from the source node.

In this case, this will be node f.

Dijkstra's algorithm is a greedy algorithm... it optimally selects the next unvisited node with the shortest estimated distance from the source at each step.

Now, we consider the node f to be visited! So we can move it to the Visited set.

And now, with a new "Visited" set, we repeat the last few steps again

Once again, we will update any "Unvisited" nodes (u.est) that are directly connected to the nodes in "Visited"

Although we've already found node b, there is another edge leading to b from node f, so we still need to check b.est.

Since the new calculated distance for b is greater than b.est, the estimate stays the same.

Now we find the Unvisited node with the smallest u.est, which is node b.

Then we can add b to the Visited set, like we did previously for f.

Again, we find all Unvisited nodes adjacent to the Visited nodes and update u.est for those Unvisited nodes.

At this stage, we now are looking at c and d.

Since neighborhoods c and d can be updated, we will adjust their estimated value to the shortest one possible based on what we have visited.

We have now found the shortest path between the source node and node c, so we can now add c to "Visited".

We find the Unvisited nodes adjacent to the Visited nodes again, and update their u.est values.

Node e can now be updated. It has a direct path from node c, so we can get e.est = c.est + edge weight = 15.

Find the adjacent Unvisited node with the smallest u.est and move it to Visited, which for this step is node e.

Again, we find the Unvisited nodes adjacent to the Visited nodes, and update their u.est values.

In this case, this is node d. The only node left is our final destination to the customer!

Our old estimate for node d is larger than our new edge that we are currently exploring, so we can replace 21 with 20.

And now, for the last time, we find the adjacent Unvisited node with the smallest u.est. Now there are no more edges to make updates with nor nodes to visit!

We have completed Dijkstra's Algorithm for this positively weighted and directed graph.

But wait a minute...

This doesn't look exactly like our solution from before!

As it turns out, Dijkstra's Algorithm finds the shortest path between a source node and ALL the nodes in a positively weighted graph.

To get our solution from before, we simply only consider the path that connects the source and target nodes.

Now that you are more familiar with Dijkstra's Algorithm, try finding the shortest path to your customer in this setting.

Click the nodes to move your car. Scroll down to see the answer.

Was this what you got?

The red lines show the right answer. The blue lines are your previous answer.