How can route software find the quickest path?

The route that looks most direct on a map may not take the least time. Navigation software can represent places as nodes and usable connections as edges. An edge's number can represent travel time, so finding the quickest route becomes a search for the smallest sum.

In the invented network, going from Start to A takes two minutes. Going directly from Start to B takes six. A connects to B in one minute and to Finish in eight; B connects to Finish in two. The drawing's line lengths do not represent those times.

Dijkstra's method starts with a total of zero at Start. It first records two for A and six for B. These totals are unsettled: a cheaper route might still be found. The smallest, A's two, can now be settled, because going farther through routes already costing at least two cannot beat it when travel times are nonnegative. Exploring A's connections discovers a better way to B: two plus one equals three. That replaces six.

B's three is now the smallest unsettled total. Continuing from B reaches Finish with five minutes, improving on the ten-minute route through A directly to Finish. Remembering which connection produced each improvement gives the route Start–A–B–Finish.

Nonnegative edge times make this increasing-cost search reliable for a fixed network. A real navigation service also needs accurate roads, restrictions and time estimates. The algorithm optimizes the supplied numbers, not unknown traffic that may occur later.