Why Shortest Path Matters
Shortest path algorithms are everywhere. Google Maps finds the fastest route between two cities. Network routers discover the cheapest path to forward packets. Social networks measure degrees of separation. Airline booking engines find the cheapest itinerary with connections.
- Navigation: GPS systems use Dijkstra (or A*) to find the fastest route between locations on a road network.
- Network routing: OSPF and IS-IS protocols use Dijkstra to compute shortest paths between routers.
- Arbitrage detection: Bellman-Ford detects negative cycles in currency exchange graphs — a negative cycle means free money.
- Flight booking: Finding the cheapest flight with at most K layovers is a modified shortest path problem.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a single source to all other nodes in a graph with non-negative edge weights. It is a greedy algorithm: at each step, it picks the unvisited node with the smallest known distance and relaxes its neighbours.
- Priority queue (min-heap): Always extracts the node with the smallest tentative distance. Use Python's
heapqwith(distance, node)tuples. - Relaxation: For each neighbour of the current node, check if going through the current node gives a shorter path. If yes, update the distance and push to the heap.
- Visited set: Once a node is popped from the heap, its shortest distance is finalized. Skip it if popped again.
Dijkstra step-by-step
- Set distance to source = 0. Set distance to all other nodes = infinity.
- Push
(0, source)onto the min-heap. - Pop the node with the smallest distance. If already visited, skip it.
- Mark it visited. For each neighbour, calculate
new_dist = dist[current] + weight. - If
new_dist < dist[neighbour], update and push(new_dist, neighbour)to the heap. - Repeat until the heap is empty.
Dijkstra Step-by-Step Visualization
Follow Dijkstra's algorithm on this 6-node weighted graph, starting from node A. At each step we show the current distances and which edge gets relaxed.
Weighted Graph (source: A)
Dijkstra Relaxation Steps
Step 1: Process A (dist=0)
Relax A→B: 0+4=4 < inf → dist[B]=4
Relax A→C: 0+2=2 < inf → dist[C]=2
Heap: [(2,C), (4,B)]
Step 2: Process C (dist=2)
Relax C→E: 2+5=7 < inf → dist[E]=7
C→B: 2+1=3 < 4 → dist[B]=3
Heap: [(3,B), (7,E)]
Step 3: Process B (dist=3)
Relax B→D: 3+3=6 < inf → dist[D]=6
B→E: 3+7=10 > 7 → no update
Heap: [(6,D), (7,E)]
Step 4: Process D (dist=6)
Relax D→E: 6+1=7 = 7 → no update
D→F: 6+6=12 < inf → dist[F]=12
Heap: [(7,E), (12,F)]
Step 5: Process E (dist=7)
Relax E→F: 7+2=9 < 12 → dist[F]=9
Heap: [(9,F)]
Final Distances from A
A=0, B=3, C=2, D=6, E=7, F=9
All nodes finalized.
Dijkstra Implementation
Here is a clean Dijkstra implementation using heapq. It returns a dictionary mapping each node to its shortest distance from the source.
Complexity
- Time: O((V + E) log V) — each node is pushed/popped from the heap at most once (O(log V) per operation), and we process every edge once.
- Space: O(V + E) — the adjacency list, distance dictionary, and heap.
Bellman-Ford Algorithm
Bellman-Ford also finds shortest paths from a single source, but unlike Dijkstra it handles negative edge weights. It can also detect negative cycles — cycles where the total weight is negative, making shortest paths undefined.
- Relax all edges V-1 times: A shortest path can have at most V-1 edges, so V-1 rounds of relaxation are enough to propagate the correct distances.
- Negative cycle detection: After V-1 iterations, do one more pass. If any distance still decreases, a negative cycle exists.
- No priority queue needed: Bellman-Ford simply iterates over the edge list. Simpler but slower than Dijkstra.
Bellman-Ford step-by-step
- Set distance to source = 0. Set distance to all other nodes = infinity.
- Repeat V-1 times: for every edge (u, v, w), if
dist[u] + w < dist[v], updatedist[v]. - Do one final pass over all edges. If any distance decreases, a negative cycle exists.
Bellman-Ford Implementation
Complexity
- Time: O(V * E) — V-1 iterations, each scanning all E edges.
- Space: O(V) — the distance array.
Dijkstra vs Bellman-Ford
| Aspect | Dijkstra | Bellman-Ford |
|---|---|---|
| Time complexity | O((V + E) log V) | O(V * E) |
| Negative weights | Not supported | Supported |
| Negative cycle detection | No | Yes |
| Data structure | Min-heap (priority queue) | Simple edge list iteration |
| Approach | Greedy | Dynamic programming |
| Best for | Non-negative weighted graphs, road networks | Graphs with negative weights, currency arbitrage |
| Implementation | More complex (heap management) | Simpler (nested loops) |
Problem: Network Delay Time
You are given a network of n nodes labelled 1 to n, and a list of directed edges times[i] = (u, v, w) where w is the time it takes for a signal to travel from node u to node v. Given a starting node k, return the minimum time for all nodes to receive the signal. If it is impossible, return -1.
Approach: This is a direct application of Dijkstra. Run Dijkstra from node k, then return the maximum distance among all nodes. If any node is unreachable (distance = infinity), return -1.
Complexity
- Time: O((V + E) log V) — standard Dijkstra.
- Space: O(V + E) — adjacency list and heap.
Problem: Cheapest Flights Within K Stops
There are n cities. You are given flights[i] = (from, to, price). Find the cheapest price from city src to city dst with at most k stops. If there is no such route, return -1.
Approach — Bellman-Ford with K+1 iterations: Instead of V-1 iterations, run only K+1 iterations (K stops means K+1 edges). At each round, relax all edges using the distances from the previous round (not the current one — this prevents using more edges than allowed).
Why copy the distance array?
If we relax edges using the current round's distances, a node updated early in the loop could be used to update another node in the same round, effectively using more edges than allowed. By copying prev = dist[:], each round only uses distances from the previous iteration, guaranteeing at most one new edge per round.
Complexity
- Time: O(K * E) — K+1 passes over all edges.
- Space: O(V) — the distance array (plus a copy).
Try It Yourself
Find Shortest Path Using Dijkstra
Given a weighted graph as an adjacency list, implement Dijkstra's algorithm to find the shortest distances from a source node to all other nodes. The starter code has the graph and test cases ready — complete the dijkstra function using heapq.
Challenge
Given a 2D grid of heights, find a path from top-left to bottom-right that minimizes the maximum absolute difference in heights between adjacent cells. You can move up, down, left, or right. Use Dijkstra where the "distance" is the max effort along the path.
(max_effort_so_far, row, col) onto the heap. The first time you reach the bottom-right corner, that is the answer.Given an n x n grid where grid[i][j] is the elevation, you start at (0,0) and want to reach (n-1,n-1). At time t, you can swim to any adjacent cell with elevation at most t. Find the minimum time to reach the destination.
max(time_to_reach_prev_cell, elevation_of_cell). Push (time, row, col) onto the heap. The first time you pop the destination, return the time.Quiz
Common Mistakes
- Using Dijkstra on graphs with negative weights. Dijkstra's greedy assumption breaks with negative edges. A "finalized" node could later be reached via a cheaper path through a negative edge. Use Bellman-Ford instead.
- Not using a min-heap in Dijkstra. Without a min-heap, you end up scanning all nodes to find the minimum distance, degrading performance to O(V^2). Always use
heapqwith(distance, node)tuples. - Forgetting the visited check in Dijkstra. The heap may contain stale entries for nodes that have already been finalized. Without checking
if u in visited: continue, you process nodes multiple times, wasting time and potentially getting wrong results. - Pushing (node, distance) instead of (distance, node) to heapq. Python's
heapqcompares tuples element by element. If you push(node, distance), the heap sorts by node ID, not by distance. Always push(distance, node). - Not copying the distance array in bounded Bellman-Ford. In problems like "cheapest flights with K stops", using the current round's distances instead of the previous round's allows paths with more edges than permitted. Always copy with
prev = dist[:].
Key Takeaways
- Dijkstra = greedy + min-heap, O((V+E) log V). Use it for shortest paths in graphs with non-negative edge weights. It is the default choice for weighted graph problems in interviews.
- Bellman-Ford = V-1 edge relaxations, O(VE). Use it when edges can have negative weights, or when you need to detect negative cycles. Slower than Dijkstra but more versatile.
- Relaxation is the core operation. Both algorithms repeatedly check: "Can I reach this neighbour faster by going through the current node?" If yes, update the distance. This is called edge relaxation.
- heapq tuples must be (distance, node). Python's heap compares the first element of the tuple. Always put the distance first so the heap correctly prioritizes the closest node.
- Know when to use which. Non-negative weights → Dijkstra. Negative weights → Bellman-Ford. Bounded hops → modified Bellman-Ford. Unweighted → BFS.
You've mastered shortest path algorithms.
Now build the career they unlock.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →