Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall)

Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall) | Algoryva

Intuition

A navigation app

A navigation app does not pick the route with the fewest turns. It picks the one with the smallest total travel time, where every road has its own cost. A short road through a traffic jam can lose to a longer empty highway.

A shortest-path algorithm answers exactly that: given a graph whose edges have costs (weights), find the path from a start to a goal with the smallest sum of costs.

First, the naive way

Use BFS and report the cost

You already know how to find the path with the fewest edges: BFS. It is tempting to reuse it and add up the weights along the way.

But fewest edges is not cheapest cost. In the graph below the direct road A–C (one edge, cost 5) beats the two-edge route A–B–C (cost 1 + 1 = 2) in BFS's eyes, so BFS returns 5 when the true answer is 2. The result is not just slow, it is wrong.

python

from collections import deque

# A-B costs 1, B-C costs 1, but the direct road A-C costs 5.
g = {"A": [("B", 1), ("C", 5)], "B": [("A", 1), ("C", 1)], "C": [("A", 5), ("B", 1)]}

def bfs_cost(g, s, t):
    q = deque([(s, 0)])
    seen = {s}
    while q:
        u, cost = q.popleft()
        if u == t:
            return cost
        for v, w in g[u]:
            if v not in seen:
                seen.add(v)
                q.append((v, cost + w))

def cheapest_bruteforce(g, s, t, seen=()):
    if s == t:
        return 0
    best = float("inf")
    for v, w in g[s]:
        if v not in seen:
            best = min(best, w + cheapest_bruteforce(g, v, t, seen + (s,)))
    return best

print(bfs_cost(g, "A", "C"))   # 5
print(cheapest_bruteforce(g, "A", "C"))   # 2

Cost: Wrong whenever edge weights differ: BFS minimises the number of edges, not the total cost.

The concept

Weights, relaxation and the family of algorithms

In a weighted graph the length of a path is the sum of its edge weights. The single-source shortest path problem asks for the distance from one start node to every other node. One tiny operation drives all the algorithms:

Relaxation: if going to u and then along edge u → v of weight w is better than the best known way to v, update it: if dist[u] + w < dist[v]: dist[v] = dist[u] + w. Every algorithm below is a strategy for which edges to relax, and in what order.
BFS: all weights equal, O(V + E).
Dijkstra: weights ≥ 0, settle the closest node first, O((V + E) log V) with a heap.
Bellman–Ford: weights may be negative; relax every edge V − 1 times, O(V·E); also detects negative cycles.
Floyd–Warshall: distances between all pairs, O(V³), only for small V (a few hundred).
DAG: with no cycles, relax in topological order for O(V + E), even with negative weights.
A negative cycle (a loop with total weight below 0) makes shortest paths undefined: you could go around forever, getting cheaper each lap.

The observation

The closest unfinished node is already final

Suppose every edge weight is zero or positive. Among all nodes whose distance is not yet final, take the one with the smallest tentative distance, u. Could some other route reach u more cheaply? Any such route must leave the finished region through some other unfinished node x, whose tentative distance is at least that of u, and then continue along edges that cannot be negative, so it cannot beat u's value.

So u's distance is final: settle it, relax its outgoing edges (which may lower its neighbours' tentative distances), and repeat with the next closest. A priority queue (heap) finds “the closest” fast. That is Dijkstra's algorithm. It is greedy in the same sense as the Greedy lesson, and it depends on no negative edges for the argument to hold.

See it move

Dijkstra on a six-node graph

Numbers on the edges are lengths; the number under each node is the best distance found so far (∞ means unknown). Each step pops the closest queued node (its distance becomes final), then relaxes its edges. Watch D: first set to 22 via B, then improved to 20 via C. Also see the stale queue entries skipped later.

See it move

Bellman–Ford with a negative edge

Dijkstra's rule assumes no edge is negative, so it can settle a node too early on a graph like this one. Bellman–Ford does not rely on that: it relaxes every edge in each round and runs at most V − 1 rounds. Watch the distances fall, and the rounds stop as soon as nothing changes.

See it move

Floyd–Warshall: every pair at once

Each cell is the best distance from i to j found so far. Trying node k as a stop-over updates the cell whenever going i → k → j is shorter. After the last k, every cell holds the shortest distance for its pair, in O(n³) time for n nodes.

Worked by hand

The same run in a table

Start at A. “Settle” means a node's distance is final.

settle	relaxations	distances after (A B C D E F)
A (0)	B = 7, C = 9, F = 14	0 7 9 ∞ ∞ 14
B (7)	C: 7 + 10 = 17 no · D: 7 + 15 = 22 yes	0 7 9 22 ∞ 14
C (9)	D: 9 + 11 = 20 yes · F: 9 + 2 = 11 yes	0 7 9 20 ∞ 11
F (11)	E: 11 + 9 = 20 yes	0 7 9 20 20 11
D (20)	E: 20 + 6 = 26 no	0 7 9 20 20 11
E (20)	nothing left to improve	0 7 9 20 20 11

1
Distances can improve before they are final
D started at 22 (through B) and dropped to 20 (through C). That is allowed: it was only *tentative* until D was settled.
2
Ties
D and E both end at 20, so either may be settled first. The distances do not depend on tie-breaking.

Implementation

Dijkstra with a heap

The heap holds (distance, node) pairs. Python's heapq cannot lower a key in place, so we push a new pair each time a distance improves, and ignore old pairs when they surface (“lazy deletion”).

Plan in plain steps

pseudocode

dist[src] = 0; heap = [(0, src)]
while the heap is not empty:
    pop (d, u); if d > dist[u]: skip it (stale)
    for each edge u → v of weight w:
        if d + w < dist[v]: dist[v] = d + w; remember parent; push (d + w, v)

python

Implementation

Negative edges: Bellman–Ford

Dijkstra's argument fails if an edge can be negative: a later detour might *reduce* a distance that was already declared final. Bellman–Ford makes no such promise. It simply relaxes every edge, over and over. A shortest path has at most V − 1 edges, so after V − 1 rounds all distances are correct. If a further round still improves something, a negative cycle must exist.

python

INF = float("inf")

def bellman_ford(n, edges, src):
    dist = [INF] * n
    dist[src] = 0
    for _ in range(n - 1):
        changed = False
        for a, b, w in edges:
             dist[a] != INF  dist[a] + w < dist[b]:
                dist[b] = dist[a] + w
                changed = 
          changed:
            
     a, b, w  edges:
         dist[a] != INF  dist[a] + w < dist[b]:
                                
     dist

 (n, edges, src):   
    g = [[]  _  (n)]
     a, b, w  edges:
        g[a].((b, w))
    dist = [INF] * n
    dist[src] = 
    done = [] * n
     _  (n):
        u = ((i  i  (n)   done[i]), key= i: dist[i])
        done[u] = 
         v, w  g[u]:
              done[v]  dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
     dist

((, [(, , ), (, , ), (, , -), (, , )], ))   
((, [(, , ), (, , -), (, , -)], ))   
neg = [(, , ), (, , ), (, , -)]
((, neg, ))   
((, neg, ))

Implementation

All pairs: Floyd–Warshall

To get the distance between every pair of nodes on a small graph, consider each node k in turn as a possible stop in the middle: can going i → k → j beat the best known i → j? After all k have been tried, every distance is final. Three nested loops, with k outermost.

python

INF = float("inf")

def floyd_warshall(n, edges):
    d = [[INF] * n for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    for a, b, w in edges:
        d[a][b] = min(d[a][b], w)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
     d

d = (, [(, , ), (, , ), (, , ), (, , )])
(d[])   
(d[][])   
(d[][])

Complexity

Costs and when to use which

Rule of thumb: unweighted → BFS; weights ≥ 0 → Dijkstra; negative weights → Bellman–Ford (or topological order on a DAG); all pairs and V ≤ 400 → Floyd–Warshall.

BFS (all weights equal)

time O(V + E)space O(V)

Each node and edge handled once.

Dijkstra with a binary heap

time O((V + E) log V)space O(V + E)

Each edge may push one heap entry (O(log V)); each node is settled once.

Bellman–Ford

time O(V · E)space O(V)

V − 1 rounds, each relaxing all E edges.

Floyd–Warshall (all pairs)

time O(V³)space O(V²)

Three nested loops over V nodes.

Shortest paths on a DAG

time O(V + E)space O(V)

Relax edges in topological order; each edge once.

Dijkstra on a dense graph with an array instead of a heap

time O(V²)space O(V)

Scan for the closest unsettled node each round; better than a heap when E is about V².

Edge cases

Unreachable nodeIts distance stays inf. Print -1 (or whatever the statement says), never the raw infinity.
Negative edge weightsDijkstra can give wrong answers. Use Bellman–Ford, or a DAG order if there are no cycles.
Negative cycleDistances through it are undefined (arbitrarily low). Bellman–Ford detects it; decide what the problem wants (usually “impossible” or a flag).
Zero-weight edgesAllowed in Dijkstra. Zero-weight cycles are harmless.
Several edges between the same pair, or self-loopsRelaxation naturally keeps the cheapest; a self-loop with positive weight never helps.
Huge weights or long pathsDistances can exceed 32 bits (10⁵ edges of 10⁹). Python is safe; use 64-bit integers elsewhere, and a sentinel like 10**18 for infinity.
Directed versus undirectedFor undirected edges add both directions to the adjacency list.
Start equals targetDistance 0, and the path is just the start node.

Common mistakes

Mistakes to avoid

Using BFS on a weighted graph.
BFS counts edges, not cost. Use Dijkstra (or Bellman–Ford) when weights differ.
Running Dijkstra with negative edges.
The “closest is final” argument breaks. Use Bellman–Ford.
Forgetting the stale-entry check if d > dist[u]: continue.
Without it correctness holds but the same node is processed many times, which can turn O((V + E) log V) into something far slower.
Putting the weight second in the heap tuple, (node, dist).
The heap orders by the first element: push (distance, node).
Floyd–Warshall with the wrong loop order.
The intermediate node k must be the outermost loop.

Recognize it in a contest

How to spot a shortest-path problem

Reach for it when the problem says or implies

“Cheapest”, “fastest”, “minimum cost/time/distance from A to B” on a network where each link has its own cost.
Moves have different prices: travel times, tolls, fuel, effort in a grid with cell costs.
“Minimum number of steps” where each step has the same cost: BFS, not Dijkstra.
A state graph with costs: nodes are (position, fuel left) or (room, keys), edges are moves with a price.
“Minimise the worst edge on the route” (a bottleneck) or other path-combination rules: a Dijkstra variant where the way costs combine changes (see the worked problem).
Negative values or “can you make an infinite profit?”: Bellman–Ford and negative cycles (currency arbitrage).

Look elsewhere when

Worked problem

Network delay time

The problem

A signal is sent from node k of a directed network of n nodes. Each entry [u, v, w] says the signal takes w time units to travel from u to v. How long until every node has received the signal? Return -1 if some node is never reached.

The time for a node to receive the signal is its shortest-path distance from k.
All nodes have received it when the slowest one has: the answer is the maximum distance.
If any distance is infinity, some node is unreachable, so return -1.

python

import heapq

def network_delay(n, times, k):
    g = [[] for _ in range(n + 1)]
    for u, v, w in times:
        g[u].append((v, w))
    dist = [float("inf")] * (n + 1)
    dist[k] = 0
    pq = [(, k)]
     pq:
        d, u = heapq.(pq)
         d > dist[u]:
            
         v, w  g[u]:
             d + w < dist[v]:
                dist[v] = d + w
                heapq.(pq, (d + w, v))
    worst = (dist[:])
     -  worst == ()  worst

((, [[, , ], [, , ], [, , ]], ))   
((, [[, , ]], ))   
((, [], ))

Worked problem

Minimise the worst edge on the route

The problem

Given an undirected weighted graph, find a path from s to t whose largest single edge weight is as small as possible (think: the narrowest bridge you must cross). Return that value, or -1 if there is no path.

This is not “sum of weights”, but the same engine works. Define the cost of a path as the maximum edge on it.
Replace d + w with max(d, w) when relaxing. Combining by max never makes a path cheaper by adding an edge, so the “closest first” argument still holds.
Stop as soon as t is popped: its value is final.

python

import heapq

def min_bottleneck(n, edges, s, t):
    g = [[] for _ in range(n)]
    for a, b, w in edges:
        g[a].append((b, w))
        g[b].append((a, w))
    best = [float("inf")] * n
    best[s] = 0
    pq = [(, s)]
     pq:
        b, u = heapq.(pq)
         b > best[u]:
            
         u == t:
             b
         v, w  g[u]:
            nb = (b, w)
             nb < best[v]:
                best[v] = nb
                heapq.(pq, (nb, v))
     -

((, [(, , ), (, , ), (, , ), (, , )], , ))   
((, [(, , )], , ))

Wrap-up

Remember this

BFS minimises edges, not cost; for weighted graphs use a shortest-path algorithm built on relaxation.
Dijkstra settles the closest unfinished node, whose distance is final when no edge is negative; a heap makes it O((V + E) log V).
Store parents to recover paths, and treat inf as “unreachable”.
Bellman–Ford handles negative edges in O(V·E) and detects negative cycles with one extra round.
Floyd–Warshall gives all pairs in O(V³); pick the algorithm from the weights and the size of the graph.

Cheat sheet

Relax: if dist[u] + w < dist[v]: dist[v] = dist[u] + w
Dijkstra: heap of (dist, node); pop; skip if d > dist[u]; relax; needs weights ≥ 0
Bellman–Ford: relax all edges V − 1 times; one more improvement ⇒ negative cycle
Floyd–Warshall: for k, for i, for j: d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Costs: BFS O(V+E) · Dijkstra O((V+E) log V) · Bellman–Ford O(VE) · Floyd O(V³)
Path: store parent[v] = u on each improvement; walk back from the target

Top traps to avoid

Using BFS on a weighted graph.
Running Dijkstra with negative edges.
Forgetting the stale-entry check if d > dist[u]: continue.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.Why can BFS give a wrong answer on a weighted graph?
2.What does relaxing the edge u → v with weight w do?
3.In the lesson's graph, what is the shortest distance from A to D?
4.What is the time complexity of Dijkstra with a binary heap on V nodes and E edges?
5.Why does Dijkstra fail with negative edge weights?
6.“Can you make an infinite profit by trading currencies in a cycle?” points to:
7.Dijkstra on edges 1->2 (1), 1->3 (4), 2->3 (2), 3->4 (1), starting at 1. What is the distance to node 4?
8.Bellman-Ford with edges 1->2 (4), 1->3 (5), 3->2 (-3), run for V-1 = 2 rounds from node 1. What is the distance to node 2?
9.Floyd-Warshall on 3 nodes (0-based) with 0->1 (3), 1->2 (4), 0->2 (10). What is dist[0][2] after the algorithm?
10.Dijkstra on the 6-node graph with edges 1-2 (7), 1-3 (9), 1-6 (14), 2-3 (10), 2-4 (15), 3-4 (11), 3-6 (2), 4-5 (6), 6-5 (9), undirected. What is the distance from 1 to 5?
11.Why can Dijkstra give wrong answers when an edge weight is negative?
12.Dijkstra with a binary heap on a graph with n nodes and m edges: what is the running time?
13.What does Floyd-Warshall compute?
14.What is the running time of Floyd-Warshall on n nodes?
15.What does one relaxation step do in shortest-path algorithms?

import heapq

INF = float("inf")

def dijkstra(n, edges, src):
    g = [[] for _ in range(n)]
    for a, b, w in edges:
        g[a].append((b, w))
        g[b].append((a, w))
    dist = [INF] * n
    parent = [-1] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                      # a stale entry: u already has a better distance
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent

def path_to(parent, t):
    path = []
    while t != -1:
        path.append(t)
        t = parent[t]
    return path[::-1]

edges = [(0, 1, 7), (0, 2, 9), (0, 5, 14), (1, 2, 10), (1, 3, 15), (2, 3, 11), (2, 5, 2), (3, 4, 6), (4, 5, 9)]
dist, parent = dijkstra(6, edges, 0)
print(dist)   # [0, 7, 9, 20, 20, 11]
print(path_to(parent, 4))   # [0, 2, 5, 4]
dist7, _ = dijkstra(7, edges, 0)
print(dist7[6])   # inf

Printing inf or treating it as a real distance.

Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall)

After this lesson you will be able to

Builds on

Unlocks

A navigation app

Use BFS and report the cost

Weights, relaxation and the family of algorithms

The closest unfinished node is already final

Dijkstra on a six-node graph

Bellman–Ford with a negative edge

Floyd–Warshall: every pair at once

The same run in a table

Dijkstra with a heap

Negative edges: Bellman–Ford

All pairs: Floyd–Warshall

Costs and when to use which

Edge cases

Mistakes to avoid

How to spot a shortest-path problem

Network delay time

Minimise the worst edge on the route

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core5 problems

Application5 problems

Challenge11 problems

Reading the code

Reading the code

Reading the code