Finding the shortest route through a map is a graph problem. When every edge has a non-negative cost, Dijkstra's algorithm discovers the cheapest paths from one starting vertex without trying every possible route.
Keep the best distance found so far
Start by assigning distance zero to the source and infinity to every other vertex. Put the source in a min-priority queue. Each queue entry represents a candidate vertex and its current known distance. Repeatedly remove the nearest candidate, then inspect its outgoing edges.
For an edge from u to v with weight w, calculate distance[u] + w. If this candidate is smaller than the best known distance to v, update that distance and remember u as the predecessor. This step is called relaxation.
Why the greedy choice is safe
When the smallest tentative distance is removed from the queue, no unseen route can make it cheaper: every remaining edge has a non-negative weight, so continuing along another path cannot reduce the cost already paid. The vertex can be treated as settled. The algorithm grows a settled region outward from the source.
A practical implementation may push a new queue entry each time a distance improves rather than decrease a key in place. When an old entry is later removed, compare it with the current distance and skip it if it is stale.
Complexity and limits
With adjacency lists and a binary heap, the running time is O((V + E) log V), where V is the number of vertices and E is the number of edges. For dense graphs, other representations may be preferable. Most importantly, negative edge weights break Dijkstra's correctness; use Bellman-Ford when negative edges are allowed and negative cycles must be detected.
To recover the actual route, follow predecessor links backward from the destination, then reverse that sequence. Distances answer how far; predecessors explain how to get there.