LESSON 23 · PATTERN GUIDE

Shortest Path

Choose a graph algorithm that matches edge weights and the path objective.

FIRST, LEARN THE PATTERNBFS finds shortest paths in unweighted graphs; Dijkstra handles nonnegative weights; Bellman-Ford can handle negative edges without negative cycles.

The prompt asks for minimum travel cost, time, effort, or number of edges between nodes.

How to approach it

Model states and transitions, choose the correct algorithm for the edge weights, and relax distances as better routes are found.

Watch out for

Dijkstra is not correct with negative edges. Some problems add constraints such as a maximum number of stops or special state dimensions.

A CLOSER EXPLANATION

A shortest-path algorithm repeatedly improves distance estimates using edges. BFS is enough when every edge has equal cost; Dijkstra selects the currently cheapest known state for nonnegative weights. Model any extra constraints—such as fuel, stops, or keys—as part of the state when a node alone is insufficient.

NOW YOU TRY

Practice question

Find the shortest path cost from A to D with edges A–B:2, A–C:5, B–C:1, B–D:4, C–D:1.

EXAMPLEAll edge weights are nonnegative.Give your answer before revealing the explanation.

Show a hint

Compare the direct-looking route A-B-D with the route through C.

Show an answer

4 via A → B → C → D.

CONNECT IT TO REAL LIFE

Shortest Path at work

A courier can travel between depots A–B in 4 minutes, A–C in 2, C–B in 1, and B–D in 3. What is the fastest known route from A to D?

Show one possible approach

A → C → B → D takes 6 minutes. With nonnegative travel times, Dijkstra's algorithm explores the closest unsettled depot next.

Practice next

Use these problem IDs to find additional practice for this pattern:

7437871514163113341976