The shortest path problem is one of the most common patterns in graph algorithms. Given a graph with weighted edges, find the path between two nodes that minimizes the total weight.

It appears in many contexts: navigation apps computing driving directions, routing packets through the internet, planning delivery routes, and a large set of coding interview problems.

Several algorithms solve this problem, and each one is designed for a different scenario. The choice depends on whether the graph is weighted, whether the weights can be negative, and whether you need distances from one source or between all pairs of nodes.

This chapter introduces the shortest path pattern, covering the core algorithms used in coding interviews: BFS for unweighted graphs, Dijkstra's algorithm for non-negative weights, and Bellman-Ford for graphs that may have negative edges.

A shortest path between two nodes in a graph is the path with the minimum total edge weight. In an unweighted graph, this means the path with the fewest edges. In a weighted graph, it means the path where the sum of edge weights is smallest.

In the unweighted graph, both paths from A to D have length 2 (A→B→D and A→C→D). In the weighted graph, A→B→D costs 4+3=7 while A→C→D costs 2+5=7. Both paths have the same total cost. If we changed C→D to weight 4, then A→C→D would become the shorter path at cost 6.

What counts as "shortest" depends on the metric. For unweighted graphs, count the edges. For weighted graphs, sum the weights.

Shortest path problems come in several flavors, and recognizing which type you are facing determines which algorithm to use.

Single-Source Shortest Path (SSSP)

Find the shortest path from one starting node to all other nodes in the graph. This is the most common type in interviews. Phrases like "starting from node K" or "from source S" indicate SSSP.

Single-Pair Shortest Path

Find the shortest path between exactly two nodes: a source and a destination. While this seems simpler than SSSP, the best known algorithms for this are the same as for SSSP. We solve the general problem and extract the specific answer.

All-Pairs Shortest Path (APSP)

Find the shortest path between every pair of nodes. This is useful when you need distances between all node pairs, like precomputing a distance matrix. Floyd-Warshall handles this case.

Most interview problems are single-source or single-pair. All-pairs is rare but appears in problems involving precomputation.

Different graph characteristics call for different algorithms. Here is a brief look at each before the templates and walkthroughs.

BFS (Breadth-First Search) works when all edges have the same weight (typically 1). It explores nodes level by level, guaranteeing the first time you reach a node is via the shortest path.

Dijkstra's Algorithm extends BFS to handle different non-negative weights. It uses a priority queue to always process the node with the smallest known distance, ensuring correctness through a greedy approach.

Bellman-Ford handles negative edge weights by relaxing all edges V-1 times. It is slower but more general, and it can detect negative cycles.

Floyd-Warshall computes all-pairs shortest paths in O(V^3) time using dynamic programming. Useful when V is small and you need all distances.

The decision tree for choosing an algorithm comes down to a few questions about the graph:

Most interview problems fall into the BFS or Dijkstra category. Bellman-Ford appears when constraints mention the number of edges or stops allowed.

When all edges have equal weight, BFS finds shortest paths naturally. The first time you reach a node, you have found the shortest path to it.

Why BFS works for unweighted graphs:

BFS explores nodes in order of their distance from the source. All nodes at distance 1 are processed before nodes at distance 2, which are processed before nodes at distance 3, and so on. This level-by-level expansion guarantees that when we first visit a node, we have arrived via a shortest path.

Time Complexity: O(V + E) where V is vertices and E is edges. Each vertex is enqueued and dequeued once. Each edge is examined once.

Space Complexity: O(V) for the queue and distance array.

Dijkstra's algorithm generalizes BFS to handle non-negative edge weights. Instead of a regular queue, it uses a priority queue to always process the node with the smallest known distance.

The key operation is edge relaxation:

We "relax" an edge by checking if going through the current node provides a shorter path to the neighbor than previously known.

Why the priority queue matters:

The priority queue ensures we process nodes in order of increasing distance. When we pop a node from the queue, we are guaranteed to have found the shortest path to it (assuming non-negative weights). This is because any alternative path would have to go through nodes with equal or greater distance.

Time Complexity: O((V + E) log V). Each vertex can be added to the priority queue multiple times, but at most E times (once per edge). Each priority queue operation is O(log V).

Space Complexity: O(V + E) for the graph representation and O(V) for the distance array and priority queue.

Bellman-Ford handles graphs with negative edge weights by taking a different approach: relax all edges V-1 times. This guarantees finding the shortest path because the longest possible shortest path has V-1 edges.

Why V-1 iterations?

A shortest path in a graph with V vertices can have at most V-1 edges (visiting each vertex once). In each iteration, Bellman-Ford guarantees that the shortest path using up to i edges is found. After V-1 iterations, all shortest paths are found.

Negative cycle detection:

If any edge can still be relaxed after V-1 iterations, a negative cycle exists. The cycle allows infinite reduction of path cost.

Time Complexity: O(V * E). We iterate V-1 times and examine all E edges in each iteration.

Space Complexity: O(V) for the distance array.

Let us trace through BFS on a simple unweighted graph.

Problem: Find shortest paths from node 0 to all other nodes.

Walkthrough:

Let us trace Dijkstra's algorithm on a weighted graph.

Problem: Find shortest paths from node A to all other nodes.

Walkthrough:

The priority queue ensures we process C (distance 1) before B (distance 4), even though B was added first.

Practical notes: