--- title: "Dijkstra's Shortest Path" description: "Finding the cheapest route through a weighted graph by always settling the nearest unsettled node next and relaxing the distances to its neighbours. Fewest hops and cheapest cost stop being the same a" 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-09-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 Finding the cheapest route through a weighted graph by always settling the nearest unsettled node next and relaxing the distances to its neighbours. Fewest hops and cheapest cost stop being the same answer once edges carry weights. 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 Dijkstra finds the cheapest route from a start to everywhere else where weights are zero or positive. You keep a table of best known distances, zero for the start and infinity elsewhere, plus the set of unsettled nodes. Each round you settle the unsettled node with the smallest best known distance. **Example.** You settle a node by relaxing its edges: compare the route through it against each neighbour best distance and keep the smaller, rewriting the table each round. Hops can lie: two hops of 50 and 50 cost 100, while three hops of 10, 10 and 10 cost 30, so the longer hop route wins and you read the route back off the table. A settled node is never revised, and you can trust that. Any rival route must leave the settled region through some unsettled node, and with no negative weights that detour already costs at least as much. Negative weights would break the promise, and plain breadth first search only counts hops, so it misses cheaper routes with more steps. **Tip.** You reach for Dijkstra whenever fewest hops and cheapest cost can disagree. Keep the table tidy, mark each newly settled node, and never reopen a settled row. **Recap.** Always settle the nearest unsettled node, relax its edges, and trust settled rows. ## 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)