5 Ways to Find the Shortest Path in a Graph

Dijkstra’s algorithm is not your only choice. Find the simplest algorithm for each situation

Photo by Caleb Jones on Unsplash.

When it comes to finding the shortest path in a graph, most people think of Dijkstra’s algorithm (also called Dijkstra’s Shortest Path First algorithm). While Dijkstra’s algorithm is indeed very useful, there are simpler approaches that can be used based on the properties of the graph. These can be very handy in competitive programming contests or coding interviews, where you might be forced to code up a shortest-path algorithm by hand. You need the simplest approach possible to reduce the possibility of bugs in your code.

In case you are not familiar with graphs or depth-first search (DFS) and breadth-first search (BFS), I recommend reading this piece.

For the following algorithms, we will assume that the graphs are stored in an adjacency list of the following form:

It is a HashMap of HashSets and stores the adjacent nodes for each node.

Furthermore, every algorithm will return the shortest distance between two nodes as well as a map that we call previous. That map holds the predecessor of every node contained in the shortest path. With this mapping, we can print the nodes on the shortest path as follows:

1. Depth-First Search (DFS)

This is probably the simplest algorithm to get the shortest path. However, there are drawbacks too. Your graph needs to be a tree or polytree. If this condition is met, you can use a slightly modified DFS to find your shortest path: