Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Connectivity and Paths

Dijkstra and Shortest Paths

Compute shortest paths in weighted graphs with Dijkstra's algorithm and a heap, reconstruct routes, see why negative weights break it, and meet Bellman-Ford and Floyd-Warshall.

BFS finds the path with the fewest edges. But roads have lengths, flights have prices and links have delays. In a weighted graph the best path is the one with the smallest total weight, and the fewest edges may be a bad choice: one long direct road can be worse than three short ones.

Dijkstra's algorithm (1956) solves the single-source shortest path problem for graphs whose weights are non-negative. It is the engine inside route planners and network routing protocols.

The idea

Keep a tentative distance dist[v] for every vertex, starting at infinity (0 for the source). Repeatedly:

  1. Pick the unfinished vertex u with the smallest tentative distance. That distance is now final.
  2. Relax every edge u โ†’ w of weight c: if dist[u] + c < dist[w], update dist[w] and remember parent[w] = u.

Why is step 1 safe? Any other route to u must pass through some unfinished vertex whose distance is at least as large, and since weights are non-negative that route can only get longer. This is exactly where negative weights would break the argument.

graph LR
  A -- 4 --> B
  A -- 1 --> C
  C -- 2 --> B
  B -- 5 --> D
  C -- 8 --> D

A to B directly costs 4, but A-C-B costs 3. A to D: A-C-B-D costs 8, the same as A-C-D.

Implementation with a heap

Finding "the vertex with the smallest tentative distance" quickly needs a priority queue. Python's heapq is a binary heap. Instead of decreasing a key, we push a new entry and skip stale ones when popped.

Python Dijkstra with heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a binary heap the running time is O((n + m) log n). The simple array version without a heap is O(nยฒ), which is actually better for very dense graphs.

A larger example and a check

Let us build a random weighted graph and confirm our results against networkx:

Python Checking against networkx

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Negative weights: Bellman-Ford

If some edges are negative, Dijkstra can fail. Bellman-Ford relaxes every edge n - 1 times. It handles negative weights, costs O(nยทm), and can detect a negative cycle (a cycle whose total weight is below zero), in which case shortest paths do not exist: you could loop forever and keep getting cheaper.

Python Bellman-Ford and negative cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All pairs: Floyd-Warshall

To get the distance between every pair of vertices, Floyd-Warshall uses dynamic programming. Let d_k[i][j] be the shortest i โ†’ j distance using only the first k vertices as intermediate stops. Then d_k[i][j] = min(d_{k-1}[i][j], d_{k-1}[i][k] + d_{k-1}[k][j]). It is a triple loop, O(nยณ), and works with negative weights (but not negative cycles).

Python Floyd-Warshall

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Which algorithm when?

Problem Algorithm Time
Unweighted, one source BFS O(n + m)
Non-negative weights, one source Dijkstra O((n + m) log n)
Negative weights, one source Bellman-Ford O(nm)
All pairs, small graph Floyd-Warshall O(nยณ)
DAG, one source Relax in topological order O(n + m)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which condition must hold for Dijkstra's algorithm to be correct?

    With non-negative weights, the unfinished vertex with the smallest distance can never be improved by a later route.
  2. 2. What is the running time of Dijkstra with a binary heap?

    Each edge relaxation may push onto the heap in O(log n).
  3. 3. What does a negative cycle do to shortest paths?

    You could circle the cycle repeatedly to reduce the total, so no minimum exists.
  4. 4. Which algorithm computes distances between all pairs of vertices with a triple loop?

    Floyd-Warshall runs in O(n^3) and allows negative edges but no negative cycles.

Summary

  • Weighted shortest paths minimize total weight, not the number of edges.
  • Dijkstra repeatedly finalizes the closest unfinished vertex and relaxes its edges; use heapq.
  • It needs non-negative weights; Bellman-Ford handles negatives and detects negative cycles.
  • Floyd-Warshall gives all-pairs distances in O(nยณ).
  • Store parent pointers to reconstruct routes.

Next: Trees and Forests