Pattern 23 of 27

Shortest Path

Find the cheapest route through a weighted graph with Dijkstra for non-negative weights, or bounded relaxation when stops are limited.

Cost: O(E log V) with a binary heap
Problems: 6

When to reach for it

Edges carry weights or costs.
The prompt asks for the minimum time, cost or effort between nodes.
Plain BFS fails because steps do not all cost the same.

How it works

Dijkstra's algorithm keeps a min-heap of tentative distances. The node popped with the smallest distance is final, because any other route to it would have to pass through something at least as far away. Relax its edges and push any improved distances. When the number of edges is capped, as in Cheapest Flights Within K Stops, running Bellman-Ford relaxation for k + 1 rounds is simpler and correct. Redefining what distance means, such as the largest single step or a product of probabilities, keeps the same structure.

The template

Written for Network Delay Time (write-up)

import heapq

def network_delay_time(times, n, k):
    adj = [[] for _ in range(n + 1)]
    for u, v, w in times:
        adj[u].append((v, w))
    dist = {}
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                  # already settled by a shorter path
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

Open in the editor Trace it line by line

Six problems, in learning order

1.Network Delay TimeLeetCode 743Dijkstra from k; the answer is the farthest settled node.Medium
2.Cheapest Flights Within K StopsLeetCode 787At most k stops: k + 1 rounds of Bellman-Ford over a copy of the distances.Medium
3.Path with Maximum ProbabilityLeetCode 1514Maximise a product of probabilities with a max-heap.Not in the curated 370 yet.Medium
4.Path With Minimum EffortLeetCode 1631A path's cost is its largest single step, still solved with Dijkstra.Medium
5.Find the City With the Smallest Number of Neighbors at a Threshold DistanceLeetCode 1334Floyd-Warshall on a small graph, or Dijkstra from every city.Medium
6.Number of Ways to Arrive at DestinationLeetCode 1976Dijkstra that also counts how many ways reach each shortest distance.Not in the curated 370 yet.Medium

What usually goes wrong

Running Dijkstra on a graph with negative edge weights.
Not skipping stale heap entries for nodes that are already settled.
Treating a node as settled when it is pushed rather than when it is popped.

Shortest Path, answered

When should I use the shortest path pattern?

Edges carry weights or costs. The prompt asks for the minimum time, cost or effort between nodes. Plain BFS fails because steps do not all cost the same.

What is the time complexity of shortest path?

O(E log V) with a binary heap. Redefining what distance means, such as the largest single step or a product of probabilities, keeps the same structure.

Which problem should I start with for shortest path?

Start with Network Delay Time (LeetCode 743, Medium). Dijkstra from k; the answer is the farthest settled node. The six problems on this page are in learning order.