Dijkstra’s Algorithm
Are you taking the long way or the short way?
It’s 6:42pm. One of my favorite shows to watch on television is Jeopardy. The problem is that it starts at 7pm, and I have to rush driving home to see it. I have three routes to take to make it in time. One route takes 15 minutes, another 25 minutes, and the last one takes 30 minutes. Which route am I going with so I can make it to watch the show? If you chose the route that takes 15 minutes, then you are correct!
This is an example of the shortest path algorithm. Thanks to Edsger Dijkstra, while taking a coffee break after shopping with his fiancé, he designed the shortest path algorithm. It is also known as Dijkstra’s algorithm.
What is Dijkstra’s algorithm?
It’s an algorithm that helps find the shortest path between two points (also called vertices), from one starting point and ending at one ending point, in a graph. The connecting lines (also called edges) to each point on the graph help determine the shortest path to an end point. The sum of each of these connecting lines to the end point make up the distance of the path. The goal is to find the least sum in the distance of a path in the graph.
The graph can be both directed or undirected. A directed graph means the arrows have a specific direction they are going in between each point. An undirected graph has no direction (no arrows) and moves more freely.
I forgot to mention — Dijkstra’s algorithm usually works the best with positive values. There is another algorithm with the same idea as Dijkstra’s algorithm, but works really well with negative values. That algorithm is the Bellman-Ford Algorithm. More about that algorithm here.
Exercise
Let’s go over an example of Dijkstra’s algorithm with the graph below:
This is a directed graph. The arrows indicate the direction of travel to the points on the graph. The points are labeled as letters: A, B, C, D, and E.
If we wanted to travel from A to C, what would be the shortest possible path?
Option 1:
A->B->E->C
Option 2:
A->C
Option 1 distance sum is equal to 65.
Option 2 distance sum is equal to 5.
Would you walk 5 miles or 65 miles to a destination? Maybe if you wanted to get your steps in, pick the 65 miles. Otherwise, I would pick 5 miles.
Option 2 is the shortest path.
Let’s try another example with the same graph above.
Find the shortest path from point A to point E.
Option 1:
A->C->B->E
Option 2:
A->B->E
Option 1 distance sum is equal to 25.
Option 2 distance sum is equal to 55.
Option 1 is the shortest path.
We see this algorithm a lot when we are using something like the Maps app on our phones to find the best shortest distance to a location. Next time you are walking to a nearby café in your area, you can use Dijkstra’s algorithm (or the very lovely and easy GPS) to find the most efficient path possible.
Sources:
Dijkstra’s Shortest Path Algorithm. (n.d.). Berkeley Electrical Engineering and Computer Sciences. Retrieved April 17, 2023, from https://inst.eecs.berkeley.edu/~cs61bl/r//cur/graphs/dijkstra-algorithm.html?topic=lab24.topic&step=3&course=
Gries, David. (2017). The shortest path algorithm. Cornell University Department of Computer Science. https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html
Klappenecker, Andreas. (n.d.). The Bellman-Ford Algorithm. [PowerPoint slides]. https://people.engr.tamu.edu/andreas-klappenecker/csce629-f17/csce411-graphs6.pdf
