Finding The Shortest Path, With A Little Help From Dijkstra

Vaidehi Joshi
Oct 17, 2017 · 17 min read
Finding the shortest path, with a little help from Dijkstra!

Graphs that weigh heavy on your mind

Before we can really get into Dijkstra’s super-famous algorithm, we need to pick up a few seeds of important information that we’ll need along the way, first.

Weighted graph: a definition
The weight of an edge represents the cost or distance between two nodes.
We can represent weighted graphs using an adjacency list.
Weighted graph as an adjacency list.

finding the shortest path between two nodes becomes much trickier when we have to take into account the weights of the edges that we’re traversing through.

Let’s take a look at an example, and this will start to become more clear. In the simple directed, weighted graph below, we have a graph with three nodes (a, b, and c), with three directed, weighted edges.

What is the shortest path between nodes A and B?

Rules of Dijkstra’s game

Dijkstra’s algorithm is unique for many reasons, which we’ll soon see as we start to understand how it works. But the one that has always come as a slight surprise is the fact that this algorithm isn’t just used to find the shortest path between two specific nodes in a graph data structure. Dijkstra’s algorithm can be used to determine the shortest path from one node in a graph to every other node within the same graph data structure, provided that the nodes are reachable from the starting node.

Dijkstra’s algorithm can be used to find the shortest path.
There are many possible paths between node A and node E.
Steps and rules to run Dijkstra’s algorithm.
  1. Once we’ve moved to the node we’re going to visit, we will check each of its neighboring nodes.
  2. For each neighboring node, we’ll calculate the distance/cost for the neighboring nodes by summing the cost of the edges that lead to the node we’re checking from the starting vertex.
  3. Finally, if the distance/cost to a node is less than a known distance, we’ll update the shortest distance that we have on file for that vertex.
Dijkstra’s algorithm, part 1
Dijkstra’s algorithm: setting things up.
Dijkstra’s algorithm, part 2
Dijkstra’s algorithm, part 3
Dijkstra’s algorithm, part 4
How did we get that number, though?

Behind the scenes of Dijkstra’s magic

We’ll continue doing the same steps for each vertex that remains unvisited. The next node we’d check in this graph would be d, as it has the shortest distance of the unvisited nodes. Only one of node d's neighbors is unvisited, which is node e, so that’s the only one that we’ll need to examine.

Dijkstra’s algorithm, part 5
Dijkstra’s algorithm, part 6
The final values from Dijkstra’s algorithm.
Retracing our steps to find the shortest path.
Dijkstra’s algorithm visualized, © Wikimedia Foundation
Dijkstra’s algorithm implemented for path-finding on a map.

Resources

For better or for worse, Dijkstra’s algorithm is one of the most well-known methods of graph traversal in the world of computer science. The bad news is that sometimes it can feel intimidating to try to understand how it works, since there are so many references to it. The good news is that there are plenty of resources out there — you just need to know which ones to start with! Here are some of my favorites.

  1. Dijkstra’s Algorithm, Computerphile
  2. Dijkstra’s Shortest Paths Algorithm for Graphs, Sesh Venugopal
  3. A Single-Source Shortest Path algorithm for computing shortest path, Professor Ileana Streinu
  4. A Note on Two Problems in Connexion with Graphs, E.W. Dijkstra

basecs

Exploring the basics of computer science, every Monday, for a year.

Vaidehi Joshi

Written by

Writing words, writing code. Sometimes doing both at once.

basecs

basecs

Exploring the basics of computer science, every Monday, for a year.