--- title: "Dijkstra's Shortest Path" description: "Dijkstra finds cheapest routes from a start in a graph with nonnegative edge weights. It settles the smallest unsettled distance and relaxes outgoing edges. A route with more edges can cost less than " canonical: https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL source: https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Dijkstra's Shortest Path Dijkstra finds cheapest routes from a start in a graph with nonnegative edge weights. It settles the smallest unsettled distance and relaxes outgoing edges. A route with more edges can cost less than one with fewer edges. Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18 Page: https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL ## Ready when they can - Run the algorithm on a small weighted graph, keeping the table of best-known distances - Say why the nearest unsettled node can be fixed and never revised - Give a graph where the fewest-hops route is not the cheapest route ## Lesson: Cheapest routes with weights Earlier, breadth-first search found routes with the fewest edges. Dijkstra minimizes total edge weight; all weights must be zero or positive. Keep best-known distances and settled marks. Initially use 0 for the start and infinity elsewhere. Each round settles the node with the smallest finite unsettled distance. A settled distance is final. Trace Dijkstra by setting the start to 0 and all other distances to infinity, meaning no route found yet. Choose an unsettled node with the smallest finite distance and mark it settled. For each outgoing edge to an unsettled neighbour, add its weight to that distance. Keep the smaller of this sum and the neighbour's old distance. Copy the updated table row, then repeat. Stop when no finite unsettled distance remains. Either node may be chosen when minima tie. **Example.** Relaxing compares the old cost with a route through the chosen node. With P settled at 4, Q at 13, and edge P to Q of weight 5, the candidate is 4 + 5 = 9. Lower Q to 9 and record P as its predecessor. A larger candidate changes nothing. On a tie, keep the predecessor. *(drawing: Q's distance falls because the route through P costs less. The boxes show an update, not the graph.)* For nonnegative weights, suppose a cheaper route to the next chosen node existed. Take the first unsettled node on that route. Relaxing its settled predecessor has already given it a best-known distance no greater than that route's prefix cost. The chosen node's distance is no larger, and the rest of the route cannot reduce cost. This rules out a cheaper route. Settled distances stay fixed; negative edges remove this guarantee. Fewest edges need not mean least cost. Between the same two nodes, a two-edge route costing 20 + 20 totals 40. A three-edge route costing 7 + 7 + 7 totals 21. Ordinary breadth-first search chooses by edge count, so it has no cheapest-cost guarantee for general weighted graphs. It does find cheapest routes when all edges have the same positive weight. Dijkstra handles differing nonnegative weights. To recover a route, keep a predecessor beside each distance. Whenever relaxation lowers a distance, replace its predecessor with the node used for that update. From a reachable target, follow predecessors back to the start, then reverse that list. For example, if R's predecessor is Q and Q's is P, the route from P to R is P, Q, R. A target still at infinity is unreachable and has no route. **Recap.** With nonnegative weights, settle the smallest finite unsettled distance, relax outgoing edges, and use predecessors to recover routes. *Lesson, examples, questions and flashcards written for this dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Breadth-First and Depth-First Search](https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy) ## Opens up - [Shortest Paths with Negative Weights and Between All Pairs](https://lightmysky.com/learn/computing/shortest-paths-with-negative-weights-and-between-all-pairs-mt_e8szFezaxO) - [Routing: How a Path Is Learned](https://lightmysky.com/learn/computing/routing-how-a-path-is-learned-mt_gyqPDrV6Uo)