internet
did you know Google Maps uses graph maths to find the fastest route?
every junction becomes a node, every road an edge with a cost — then a classic algorithm finds the cheapest path through.
numbers are travel costs — traffic, distance, tolls. the algorithm hunts the cheapest chain.
the idea
a city’s road network can be written as maths: junctions are nodes, roads are edges, and each edge carries a cost like time or distance. finding the fastest route means finding the cheapest path through that graph.
how it works
junctions become nodes. roads become edges. each edge gets a cost: its length, the current traffic, the speed limit, whether there’s a toll.
go deeper
a city is a network
strip away the buildings and a city is just places connected by roads. that structure — things and connections — is what mathematicians call a graph.
once a map is a graph, routing stops being geography and becomes a puzzle computers are extremely good at.
nodes, edges, costs
junctions become nodes. roads become edges. each edge gets a cost: its length, the current traffic, the speed limit, whether there’s a toll.
a route is a chain of edges, and its total cost is just the sum. the fastest route is the chain with the smallest total — the shortest path.
route cost = Σ edge costs
dijkstra’s neat idea
in 1956, edsger dijkstra described an elegant search: start at your origin, and repeatedly visit the cheapest not-yet-visited node, updating the cost of reaching its neighbours.
when the destination becomes the cheapest unvisited node, you’re done — no other unfinalised route could possibly beat it.
modern routing adds clever shortcuts and pre-computation to handle hundreds of millions of edges, but the heart of it is this sixty-year-old idea.
dist[v] = min(dist[v], dist[u] + cost(u → v))
things to wonder about next
- live traffic just changes edge costs — the “fastest” route is re-solved constantly as conditions shift.
- a* search adds a compass: it prefers exploring nodes that head towards the destination.
- the same maths routes internet packets, plans circuit boards, and sequences dna.
sources & further reading
concepts: graph theory · shortest path · dijkstra’s algorithm
5 minute read