A Common-Sense Guide to Data Structures and Algorithms

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 the graph. Let’s walk through this algorithm step by step.