Dijkstra’s Algorithm, explained.
Dijkstra’s algorithm finds shortest paths from a source in a graph with nonnegative edge weights by repeatedly settling the smallest tentative distance.
Why it happens
An authored five-node undirected graph starts at A. Each step settles the lowest-cost unvisited node and relaxes adjacent edges. The least-cost A-to-E route is A–B–C–D–E with total weight seven.
Dijkstra’s algorithm finds shortest paths from a source in a graph with nonnegative edge weights by repeatedly settling the smallest tentative distance.
Read the result
Tentative distances are upper bounds that can improve. Settled distances are certified only because every edge weight is nonnegative.
A worked example
A cheap route with several edges
Settle A and compare its direct tentative costs to B and C in the weighted graph.
Settle B to improve C through the cheaper two-edge route, then continue through C and D.
Settle E at total cost seven and trace A–B–C–D–E rather than counting connections as if every edge had equal cost.
OPTIONAL DEEPER DETAILGo deeper: inside the model
Inside this model
An authored five-node undirected graph starts at A. Each step settles the lowest-cost unvisited node and relaxes adjacent edges. The least-cost A-to-E route is A–B–C–D–E with total weight seven.
Where this idea is useful
A practical use
Use weighted travel cost rather than the number of connections when routes differ in time or expense.
A common misconception
“The path with the fewest connections is always cheapest.”
Unequal edge weights make total weight, rather than edge count, the relevant objective. A longer sequence can have a lower cost.
What this explanation leaves out
- The graph is small, static and has nonnegative weights; negative edges invalidate the settling argument.
Can this settling logic handle negative edges?
No. A negative edge can later create a cheaper route to a supposedly final node, invalidating the argument used here.
Are you minimising the number of steps or their actual accumulated cost?
Associated thinkers
Associations marked provisional are awaiting source review.
Further reading
Explore the original research or the teaching reference behind this experiment.