basecs
Published in

basecs

Finding The Shortest Path, With A Little Help From Dijkstra

Finding the shortest path, with a little help from Dijkstra!

Graphs that weigh heavy on your mind

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.

What is the shortest path between nodes A and B?

Rules of Dijkstra’s game

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. Every time that we set out to visit a new node, we will choose the node with the smallest known distance/cost to visit first.
  2. Once we’ve moved to the node we’re going to visit, we will check each of its neighboring nodes.
  3. 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.
  4. 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

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

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store