Every time you open a navigation app and ask for directions, an algorithm is computing the shortest path from your current location to your destination.

Behind the scenes, it is exploring a massive graph of roads, intersections, and travel times to find the route that gets you there fastest. The same fundamental problem appears everywhere: routing packets through the internet, planning logistics for delivery trucks, finding connections in social networks, and of course, solving coding interviews.

The shortest path problem is deceptively simple to state: given a graph with weighted edges, find the path between two nodes that minimizes the total weight.

But this simplicity hides a rich landscape of algorithms, each designed for different scenarios. Use the wrong algorithm, and your solution might be incorrect or impossibly slow. Use the right one, and seemingly complex problems become straightforward.

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

What Is Shortest Path?

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. Same total cost, but if we changed C→D to weight 4, then A→C→D would become the shorter path at cost 6.

The key insight is that "shortest" depends on your metric. For unweighted graphs, count the edges. For weighted graphs, sum the weights.

Types of Shortest Path Problems

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. When you see "starting from node K" or "from source S", think 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.

Algorithm Overview

Different graph characteristics call for different algorithms. Here is the landscape:

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.

When to Use Each Algorithm

The decision tree for choosing an algorithm is straightforward:

Key questions to ask:

In interviews, most problems fall into the BFS or Dijkstra category. Bellman-Ford appears when constraints mention the number of edges or stops allowed.

BFS Template for Unweighted Graphs

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 Template

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 Algorithm Template

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.

Example 1: BFS on Unweighted Graph

Let us trace through BFS on a simple unweighted graph.

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

Walkthrough:

Example 2: Dijkstra on Weighted Graph

Now let us trace Dijkstra's algorithm on a weighted graph.

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

Walkthrough:

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

Complexity Comparison

Practical notes: