Finding the shortest path between two points on a graph is a common problem in data structures, especially when dealing with optimization.
A graph is a series of nodes connected by edges. Graphs can be weighted (edges carry values) and directional (edges have direction).
Some applications of this are flight path optimization or 6 degrees of Kevin Bacon.
Dijkstra’s Algorithm
The most common solution for this problem is Dijkstra’s algorithm which updates the shortest path between the current node and all of its neighbors.
After updating the distance of all of the neighbors it moves to the node with the lowest distance and repeats the process with all unvisited neighbors. This process continues until the entire graph has been visited.
Step 0:
Our graph needs to be setup so that we can record the required values. On any edge we have the distance between the two nodes it connects. On any node we have its shortest distance from the starting node.
Let's set the value on every node to positive infinity, and set the value on the starting node to zero.
Step 1:
Look at all nodes directly adjacent to the starting node. The values carried by the edges connecting the start and these adjacent nodes are the shortest distances to each respective node.
Record these distances on the node - overwriting infinity - and also cross off the nodes, meaning that their shortest path has been found.
Step 2:
Select one of the nodes which has had its shortest path calculated, we’ll call this our pivot. Look at the nodes adjacent to it (we’ll call these our destination nodes) and the distances separating them.
For every destination node:
- If the value in the pivot plus the edge value connecting it totals less than the destination node’s value, then update its value, as a new shorter path has been found.
- If all routes to this destination node have been explored, it can be crossed off.
Step 3:
Repeat step 2 until all nodes have been crossed off. We now have a graph where the values held in any node will be the shortest distance to it from the start node.