Graph Shortest Path Pattern

The shortest path problem is one of the most fundamental graph problems: given a weighted graph, find the path from a source to a destination (or all destinations) with the minimum total weight. Different algorithms handle different graph constraints, and choosing the right one is half the battle in interviews.

Core Concept

In an unweighted graph, BFS gives shortest paths because it explores nodes level by level (each level = one more edge). But when edges have weights (costs, distances, times), BFS no longer works because a path with fewer edges might have a higher total cost. We need algorithms that account for edge weights.

Unweighted (BFS works):       Weighted (BFS fails):
A --1-- B --1-- D              A --1-- B --10-- D
|               |              |                |
1               1              1                1
|               |              |                |
C ------1------ E              C -------2------ E

BFS: A→B→D (2 edges)           BFS: A→B→D (cost 11)
Optimal: A→B→D (cost 2)        Optimal: A→C→E→D (cost 4)

Key Algorithms

1. Dijkstra's Algorithm (Most Important for Interviews)

Dijkstra finds shortest paths from a source to all nodes in a graph with non-negative edge weights. It uses a min-heap (priority queue) to always process the node with the smallest known distance next.

Algorithm:
1. Initialize: dist[source] = 0, dist[all others] = infinity
2. Push (0, source) onto min-heap
3. While heap is not empty:
   a. Pop (cost, node) with minimum cost
   b. If cost > dist[node], skip (already found a better path)
   c. For each neighbor of node:
      newCost = cost + edgeWeight
      If newCost < dist[neighbor]:
        dist[neighbor] = newCost
        Push (newCost, neighbor) onto heap

The "skip if cost > dist[node]" check is the lazy deletion optimization. Instead of decreasing a key in the heap (which is complex), we simply push a new entry and skip stale ones when popped.

2. Bellman-Ford Algorithm

Bellman-Ford handles negative edge weights and can detect negative cycles. It relaxes ALL edges V-1 times. It is slower than Dijkstra but more general.

Algorithm:
1. Initialize: dist[source] = 0, dist[all others] = infinity
2. Repeat V-1 times:
   For each edge (u, v, weight):
     If dist[u] + weight < dist[v]:
       dist[v] = dist[u] + weight
3. (Optional) One more pass to detect negative cycles:
   If any edge can still be relaxed, a negative cycle exists

Interview use case: The classic "cheapest flights within K stops" problem uses a modified Bellman-Ford where you only relax K+1 times (K stops = K+1 edges).

3. BFS for Unweighted Shortest Path

When all edges have equal weight (or weight = 1), BFS gives shortest paths directly. Each BFS level corresponds to one more edge, so the first time you reach a node is the shortest path. This is covered in depth in the Graphs (BFS/DFS) pattern.

4. Modified Dijkstra (With Constraints)

Many interview problems add constraints to shortest path, such as:

• At most K stops (Cheapest Flights Within K Stops)
• Minimum probability path (Path with Maximum Probability)
• Track additional state beyond just distance

The key technique: expand the state in your priority queue. Instead of just (cost, node), push (cost, node, stopsRemaining) or (cost, node, fuelLeft). The dist array also becomes multi-dimensional: dist[node][stops].

Modified Dijkstra with K stops:
State: (cost, node, stopsLeft)
Push (0, source, K) onto heap
While heap not empty:
  Pop (cost, node, stops)
  If node == destination: return cost
  If stops == 0: continue (no more stops allowed)
  For each neighbor:
    newCost = cost + weight
    If newCost < dist[neighbor][stops-1]:
      dist[neighbor][stops-1] = newCost
      Push (newCost, neighbor, stops-1)

Choosing the Right Algorithm

| Scenario | Algorithm | Why | |----------|-----------|-----| | Unweighted graph | BFS | Each edge = 1, level-order gives shortest path | | Non-negative weights | Dijkstra | Greedy with priority queue, O((V+E) log V) | | Negative weights possible | Bellman-Ford | Handles negatives, O(VE) | | K stops / bounded hops | Bellman-Ford (K+1 iterations) | Natural fit for hop-limited relaxation | | Constrained state | Modified Dijkstra | Expand state in priority queue | | Dense graph, no heap | Floyd-Warshall | All-pairs, O(V^3), rarely in interviews |

Common Mistakes

1. Using Dijkstra with negative edges -- Dijkstra's greedy approach assumes once a node is settled (popped from the heap), its distance is final. Negative edges violate this assumption and produce wrong answers. If the problem mentions negative weights or costs that can decrease, use Bellman-Ford instead.
2. Forgetting the "skip stale entries" check in Dijkstra -- Without the if cost > dist[node]: continue check, you process nodes multiple times with suboptimal distances. This does not produce wrong answers but degrades performance from O((V+E) log V) to potentially O(V^2 log V) on dense graphs.
3. Initializing dist array with 0 instead of infinity -- Every non-source node must start with distance = infinity (or a very large number). Starting with 0 means the algorithm thinks it has already found a zero-cost path to every node, so no relaxation occurs.
4. Not tracking visited/settled nodes properly -- In basic Dijkstra, once a node is popped from the heap, its shortest distance is finalized. But in modified Dijkstra with extra state (e.g., K stops), a node might be reached multiple times with different remaining stops. You need dist[node][stops] rather than just dist[node].
5. Off-by-one in Bellman-Ford iterations for K stops -- If the problem says "at most K stops," you need K+1 edge relaxations (K stops means traversing K+1 edges). Running only K iterations gives paths with at most K-1 stops. Also, you must use the distances from the previous iteration (not the current one) to avoid relaxing more edges than intended in a single pass.
6. Using Python list as a priority queue -- Using a sorted list or repeatedly calling min() on a list gives O(n) per extraction instead of O(log n). Always use heapq for Dijkstra in Python. Similarly, do not use a plain queue or deque for weighted shortest path -- BFS only works when all weights are equal.