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.

🗺️
Real-world applications
Why interviewers love shortest path
  • 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.
BFS vs Dijkstra:
BFS finds shortest paths in unweighted graphs (every edge costs 1). When edges have different weights, you need Dijkstra or Bellman-Ford. This lesson covers both weighted-graph algorithms.

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.

⚡
Core mechanism
Priority queue + relaxation = Dijkstra
  • Priority queue (min-heap): Always extracts the node with the smallest tentative distance. Use Python's heapq with (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

  1. Set distance to source = 0. Set distance to all other nodes = infinity.
  2. Push (0, source) onto the min-heap.
  3. Pop the node with the smallest distance. If already visited, skip it.
  4. Mark it visited. For each neighbour, calculate new_dist = dist[current] + weight.
  5. If new_dist < dist[neighbour], update and push (new_dist, neighbour) to the heap.
  6. 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)

4 2 3 1 7 5 1 2 6 A B C D E F dist=0 dist=inf dist=inf dist=inf dist=inf dist=inf
Source / current Unvisited Red numbers = edge weights

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.

Key insight — why the greedy choice works:
Because all edge weights are non-negative, once a node is popped from the min-heap, no future path through an unvisited node can be shorter. This is why Dijkstra fails with negative weights — a later path through a negative edge could beat the "finalized" distance.

Dijkstra Implementation

Here is a clean Dijkstra implementation using heapq. It returns a dictionary mapping each node to its shortest distance from the source.

Dijkstra with heapq Python
Output
A → A: 0 A → B: 3 A → C: 2 A → D: 6 A → E: 7 A → F: 9

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.

🔄
Core mechanism
V-1 iterations over all edges
  • 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

  1. Set distance to source = 0. Set distance to all other nodes = infinity.
  2. Repeat V-1 times: for every edge (u, v, w), if dist[u] + w < dist[v], update dist[v].
  3. Do one final pass over all edges. If any distance decreases, a negative cycle exists.

Bellman-Ford Implementation

Bellman-Ford Python
Output
Negative cycle: False A → A: 0 A → B: 3 A → C: 2 A → D: 6 A → E: 7 A → F: 9 --- Graph with negative edge --- Negative cycle: False S → A: 5 S → B: 2 S → C: 4 S → S: 0

Complexity

  • Time: O(V * E) — V-1 iterations, each scanning all E edges.
  • Space: O(V) — the distance array.
When to use Bellman-Ford:
Use Bellman-Ford only when the graph has negative edge weights, or when you need to detect negative cycles. For graphs with all non-negative weights, Dijkstra is strictly faster: O((V+E) log V) vs O(VE).

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

📡
Dijkstra application
LeetCode 743 — asked at Google, Amazon, Bloomberg

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.

Network Delay Time — Dijkstra Python
Output
Test 1: 2 Test 2: -1 Test 3: 0 Test 4: 14

Complexity

  • Time: O((V + E) log V) — standard Dijkstra.
  • Space: O(V + E) — adjacency list and heap.

Problem: Cheapest Flights Within K Stops

✈️
Modified Bellman-Ford
LeetCode 787 — asked at Amazon, Microsoft, Airbnb

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).

Cheapest Flights Within K Stops — Bellman-Ford Python
Output
Test 1: 200 Test 2: 500 Test 3: 6 Test 4: -1 Test 5: 3

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

Push yourself further
Challenge 1: Path With Minimum Effort (LeetCode 1631)

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.

Use Dijkstra with a twist: instead of summing edge weights, track the maximum edge weight (abs height difference) along the path. Push (max_effort_so_far, row, col) onto the heap. The first time you reach the bottom-right corner, that is the answer.
Challenge 2: Swim in Rising Water (LeetCode 778)

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.

Use Dijkstra where the "distance" to each cell is the minimum time needed to reach it. The time to enter a cell is 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

Question 1 of 5
What data structure does Dijkstra's algorithm use to efficiently select the next node to process?
Question 2 of 5
Why does Dijkstra's algorithm fail on graphs with negative edge weights?
Question 3 of 5
How many times does Bellman-Ford iterate over all edges to guarantee correct shortest distances?
Question 4 of 5
In the Cheapest Flights Within K Stops solution, why do we copy the distance array at each iteration?
Question 5 of 5
What is the time complexity of Dijkstra's algorithm using a binary min-heap?
0
/5
Great work! You understand shortest path algorithms.

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 heapq with (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 heapq compares 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.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →