Shortest Paths: Dijkstra, Bellman-Ford, and Floyd-Warshall

BFS finds the shortest path in an unweighted graph because every edge costs the same, so the first arrival is always the shortest. The moment edges carry different weights, that guarantee breaks — a path through more edges can still be cheaper than a path through fewer, heavier ones. This lesson covers the three workhorse algorithms for weighted shortest paths, each suited to a different shape of problem.

What you’ll learn

Dijkstra’s algorithm: a greedy, heap-driven search for single-source shortest paths when every weight is non-negative.
Bellman-Ford: slower but strictly more general — handles negative edge weights and can detect a negative cycle.
Floyd-Warshall: a dynamic-programming sweep that computes shortest paths between every pair of nodes at once.
Which one to reach for, based on graph size, edge weights, and whether you need one source or every pair.

Dijkstra’s algorithm: greedy + a min-heap

Dijkstra keeps a min-heap of (distance, node)(distance, node) pairs and always expands the closest unfinalized node next. Once a node is popped from the heap with its true shortest distance, that distance can never improve — which is exactly why negative weights break it: a “closest” node popped early could later be beaten by a path through a negative edge that hasn’t been discovered yet.

dijkstra.py

import heapq
from collections import defaultdict
 
 
def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))   # remove this line for a DIRECTED graph
 
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]          # (distance so far, node)
 
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue              # a shorter distance was already found -- stale entry
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist          # relax the edge
                heapq.heappush(heap, (new_dist, neighbor))
 
    return dist
 
 
n = 5
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print("shortest distances from 0:", dijkstra(n, edges, 0))

dijkstra.py

import heapq
from collections import defaultdict
 
 
def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))   # remove this line for a DIRECTED graph
 
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]          # (distance so far, node)
 
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue              # a shorter distance was already found -- stale entry
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist          # relax the edge
                heapq.heappush(heap, (new_dist, neighbor))
 
    return dist
 
 
n = 5
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print("shortest distances from 0:", dijkstra(n, edges, 0))

diagram Weighted graph -- Dijkstra relaxes the cheap 0-2-1 path before 0-1 mermaid

  graph LR
    N0((0)) -- "4" --> N1((1))
    N0 -- "1" --> N2((2))
    N2 -- "2" --> N1
    N1 -- "1" --> N3((3))
    N2 -- "5" --> N3
    N3 -- "3" --> N4((4))

Even though the direct edge 0 -> 10 -> 1 costs 44, Dijkstra finds that 0 -> 2 -> 10 -> 2 -> 1 only costs 1 + 2 = 31 + 2 = 3 — cheaper. Because the heap always pops the globally closest unfinalized node next, this relaxation happens before node 11 is ever finalized at the (wrong) distance 44.

Bellman-Ford: handles negative weights, detects negative cycles

Instead of being greedy, Bellman-Ford brute-forces it: relax every edge, V - 1V - 1 times. After V - 1V - 1 rounds, every shortest path (which can use at most V - 1V - 1 edges in a graph with no negative cycle) is guaranteed correct. One extra round that still finds an improvement means a negative cycle exists — distances would keep shrinking forever.

bellman_ford.py

def bellman_ford(n, edges, source):
    dist = [float("inf")] * n
    dist[source] = 0
 
    for _ in range(n - 1):               # V-1 rounds is enough for any negative-cycle-free graph
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # One more round: any further improvement means a negative cycle exists.
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            return None, True             # (distances, has_negative_cycle)
 
    return dist, False
 
 
n = 5
# Directed, weighted edges -- Bellman-Ford handles negative weights directly.
edges = [(0, 1, 4), (0, 2, 1), (2, 1, -3), (1, 3, 2), (2, 3, 5), (3, 4, 1)]
distances, has_cycle = bellman_ford(n, edges, 0)
print("negative cycle?", has_cycle)
print("shortest distances from 0:", distances)

bellman_ford.py

def bellman_ford(n, edges, source):
    dist = [float("inf")] * n
    dist[source] = 0
 
    for _ in range(n - 1):               # V-1 rounds is enough for any negative-cycle-free graph
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # One more round: any further improvement means a negative cycle exists.
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            return None, True             # (distances, has_negative_cycle)
 
    return dist, False
 
 
n = 5
# Directed, weighted edges -- Bellman-Ford handles negative weights directly.
edges = [(0, 1, 4), (0, 2, 1), (2, 1, -3), (1, 3, 2), (2, 3, 5), (3, 4, 1)]
distances, has_cycle = bellman_ford(n, edges, 0)
print("negative cycle?", has_cycle)
print("shortest distances from 0:", distances)

Floyd-Warshall: all-pairs shortest paths

When you need the shortest distance between every pair of nodes at once (not just from one source), Floyd-Warshall’s triple-nested loop dynamic program does it directly. The recurrence considers, for each pair (i, j)(i, j), whether routing through an intermediate node kk shortens the known path:

dist[i][j] = \min\bigl(dist[i][j],\ dist[i][k] + dist[k][j]\bigr)

floyd_warshall.py

def floyd_warshall(n, edges):
    INF = float("inf")
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
 
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # keep the cheaper edge if there are duplicates
 
    for k in range(n):                    # k = the intermediate node allowed in this pass
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    return dist
 
 
n = 4
edges = [(0, 1, 3), (0, 3, 7), (1, 2, 1), (2, 3, 2)]
all_pairs = floyd_warshall(n, edges)
for row in all_pairs:
    print(row)
print("shortest 0 -> 3 via node 2:", all_pairs[0][3])   # 3 + 1 + 2 = 6, beats the direct 7

floyd_warshall.py

def floyd_warshall(n, edges):
    INF = float("inf")
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
 
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)   # keep the cheaper edge if there are duplicates
 
    for k in range(n):                    # k = the intermediate node allowed in this pass
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    return dist
 
 
n = 4
edges = [(0, 1, 3), (0, 3, 7), (1, 2, 1), (2, 3, 2)]
all_pairs = floyd_warshall(n, edges)
for row in all_pairs:
    print(row)
print("shortest 0 -> 3 via node 2:", all_pairs[0][3])   # 3 + 1 + 2 = 6, beats the direct 7

Which one to use

Algorithm	Handles negative weights?	Detects negative cycles?	Complexity	Best for
Dijkstra	No	No	$O((V + E) \log V)$	Single source, non-negative weights, large sparse graphs
Bellman-Ford	Yes	Yes	$O(V \cdot E)$	Single source, possible negative edges, or you must detect a negative cycle
Floyd-Warshall	Yes	Yes (diagonal goes negative)	$O(V^3)$	All-pairs shortest paths, small/dense graphs (roughly $V \lesssim 400$ )

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 743 — Network Delay Time · Medium

Problem. Given directed weighted edges times[i] = [u, v, w]times[i] = [u, v, w], nn nodes and a source kk, return the time for a signal from kk to reach all nodes, or -1-1 if some node is unreachable.

Constraints. 1 <= k <= n <= 1001 <= k <= n <= 100, 1 <= len(times) <= 60001 <= len(times) <= 6000, 0 <= w <= 1000 <= w <= 100.

Examples. times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 gives 22 · times = [[1,2,1]], n = 2, k = 2times = [[1,2,1]], n = 2, k = 2 gives -1-1

Editorial

Dijkstra’s invariant: because all weights are non-negative, the first time a node is popped from a min-heap its distance is final — nothing still in the heap could reach it more cheaply.

Time $O(E \log V)$ . Space $O(V + E)$ .

The if node in dist: continueif node in dist: continue line is doing real work. A node can be pushed several times with different tentative distances; this check discards the stale ones and replaces a separate visited set. Omitting it does not give wrong answers — the first pop already set the correct distance — but it re-expands neighbours needlessly.

The -1-1 case is reachability: len(dist) < nlen(dist) < n means the signal never arrived somewhere. ([[1,2,1]], 2, 2)([[1,2,1]], 2, 2) starts at node 2, which has no outgoing edges, so node 1 is unreachable.

Note this requires non-negative weights. With a negative edge the first-pop invariant fails, and you need Bellman-Ford — which is the next problem’s territory.

Follow-ups: “Negative weights?” — Bellman-Ford, $O(VE)$ , and it also detects negative cycles. “All-pairs shortest paths?” — Floyd-Warshall at $O(V^3)$ , fine for n = 100n = 100. “Why does the first pop finalise a node?” — the non-negativity argument; be ready to state it. “Return the paths?” — store a predecessor per node.

LC 787 — Cheapest Flights Within K Stops · Medium

Problem. Given flights [from, to, price][from, to, price], find the cheapest price from srcsrc to dstdst using at most kk stops. Return -1-1 if there is no such route.

Constraints. 1 <= n <= 1001 <= n <= 100, 0 <= len(flights) <= n * (n - 1) / 20 <= len(flights) <= n * (n - 1) / 2, 0 <= k < n0 <= k < n.

Examples. n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 gives 700700 · n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 gives 200200, and with k = 0k = 0 gives 500500

Editorial

The hop limit is what makes Dijkstra a poor fit: it finalises nodes by cost, but the cheapest way to reach a node may use too many stops to be extendable. Bellman-Ford is naturally suited, because its rounds correspond exactly to edge counts.

Time $O(k \times E)$ . Space $O(n)$ .

The third case, k = 0k = 0, allows a single edge — so the direct 0 -> 20 -> 2 flight at 500500 beats the two-hop 200200.

Dijkstra can be adapted by carrying (cost, node, stops)(cost, node, stops) in the heap and allowing a node to be revisited with fewer stops, but the state space grows and the bookkeeping is easier to get wrong.

Follow-ups: “Why not plain Dijkstra?” — the finalisation argument above; the most likely question. “Detect negative cycles?” — run one extra round; any further improvement proves a negative cycle. “Exactly kk stops?” — read the answer from round k + 1k + 1 only. “Very large kk?” — once k >= n - 1k >= n - 1 the limit is irrelevant and plain Dijkstra applies.

LC 1631 — Path With Minimum Effort · Medium

Problem. Given a grid of heights, a route’s effort is the maximum absolute height difference between consecutive cells on it. Return the minimum effort to travel from the top-left to the bottom-right, moving in 4 directions.

Constraints. 1 <= rows, cols <= 1001 <= rows, cols <= 100, 1 <= heights[i][j] <= 10^61 <= heights[i][j] <= 10^6.

Examples. [[1,2,2],[3,8,2],[5,3,5]][[1,2,2],[3,8,2],[5,3,5]] gives 22 · [[1,2,3],[3,8,4],[5,3,5]][[1,2,3],[3,8,4],[5,3,5]] gives 11 · a grid with a zero-difference route gives 00

Editorial

Dijkstra is usually taught with additive costs, but it works for any path cost that is monotone non-decreasing as the path extends. max()max() qualifies: adding a step can only keep the effort the same or raise it, never lower it. So the first-pop-is-final invariant still holds.

Time $O(rc \log(rc))$ . Space $O(rc)$ .

The only change from a standard Dijkstra is the relaxation:

python

ne = max(e, abs(height_difference))     # instead of e + weight

python

ne = max(e, abs(height_difference))     # instead of e + weight

That generalisation — “Dijkstra needs monotonicity, not addition” — is the transferable insight, and it also covers minimax and bottleneck path problems generally.

Two alternatives worth naming:

Binary search + BFS. Guess a threshold effort, then check with BFS/DFS whether the destination is reachable using only steps within it. That is binary search on the answer at $O(rc \log(\max h))$ , and many find it easier to reason about.
Union-find. Sort all edges by difference and union them in order until the corners connect; the last edge’s difference is the answer — essentially building a minimum spanning tree, which is Kruskal’s.

[[3]][[3]] gives 00 — a single cell needs no moves.

Follow-ups: “Why does Dijkstra still work?” — the monotonicity argument; the expected question. “Do it with binary search?” — the alternative above. “With union-find?” — the Kruskal framing. “8 directions?” — extend the offsets; nothing else changes.

LeetCode problem set

#	Problem	Difficulty	The twist
743	Network Delay Time	Medium	Dijkstra straight from the template above: how long until a signal reaches every node from one source
787	Cheapest Flights Within K Stops	Medium	A Bellman-Ford variant capped at `K + 1K + 1` relaxation rounds instead of `V - 1V - 1`
1631	Path With Minimum Effort	Medium	Dijkstra where the “distance” being minimized is the maximum edge weight along the path, not the sum
1334	Find the City With the Smallest Number of Neighbors at a Threshold Distance	Medium	Floyd-Warshall’s all-pairs table, then count reachable cities per city
778	Swim in Rising Water	Hard	Dijkstra-style: a min-heap greedily expanding to the lowest-elevation unvisited cell, minimizing the maximum value on the path

Recap

Dijkstra: greedy + min-heap, $O((V + E) \log V)$ , but only correct when every weight is non-negative.
Bellman-Ford: relax every edge $V - 1$ times, $O(V \cdot E)$ ; a VV-th round that still improves something means a negative cycle.
Floyd-Warshall: triple loop with kk outermost, $O(V^3)$ , computes every pair’s shortest distance in one pass.
Default to Dijkstra; drop to Bellman-Ford for negative edges or cycle detection; reach for Floyd-Warshall only when you need all-pairs distances on a graph small enough for $O(V^3)$ .

With traversal, components, and weighted shortest paths covered, you have the core toolkit for nearly every graph question that shows up in interviews and competitive programming alike.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Shortest Paths: Dijkstra, Bellman-Ford, and Floyd-Warshall

What you’ll learn

Dijkstra’s algorithm: greedy + a min-heap

Bellman-Ford: handles negative weights, detects negative cycles

Floyd-Warshall: all-pairs shortest paths

Which one to use

Practice — real LeetCode problems

LC 743 — Network Delay Time · Medium

LC 787 — Cheapest Flights Within K Stops · Medium

LC 1631 — Path With Minimum Effort · Medium

LeetCode problem set

Recap

Was this page helpful?