O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Dijkstra’s Algorithm

There are numerous algorithms for solving the shortest path problem, and one really interesting one was discovered by Edsger Dijkstra (pronounced “dike’ struh”) in 1959. Unsurprisingly, this algorithm is known as Dijkstra’s algorithm.

Here are the rules of Dijkstra’s algorithm (don’t worry—they’ll become clearer when we walk through our example):

  1. We make the starting vertex our current vertex.
  2. We check all the vertices adjacent to the current vertex and calculate and record the weights from the starting vertex to all known locations.
  3. To determine the next current vertex, we find the cheapest unvisited known vertex that can be reached from our starting vertex.
  4. Repeat the first three steps until we have visited every vertex in ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required