The mela on the far side of the valley starts in half an hour, and your uncle has drawn you a map of the trails. Beside every trail he has written how many minutes it takes to walk: 9 to the bazaar, 6 down to the old water mill, 15 straight along the ridge to the temple, and so on, until the mela ground on the far right.
There are trails everywhere, and some of the quick-looking ones are slow. Which way should you go? Try it before reading on.
Guess first: how many different routes are there from Home to the Mela, never passing the same place twice?
Pick an answer to see why.
Try it
Most people first try the routes that look short. The ridge trail goes straight to the Temple, and from there it is two trails to the Mela: Home, Temple, Bridge, Mela takes 15 + 9 + 8 = 32 minutes. That uses only three trails, as few as any route can. But the quickest route uses five: Home, Mill, Pond, Chautari, Bridge, Mela, 6 + 7 + 5 + 3 + 8 = 29 minutes. It goes down the valley and back up, the long way round on the drawing, but quicker by the clock.
Which route did you find quickest? If you found 29 minutes, how do you know nothing beats it?
Pick an answer to see why.
Too many routes to try
How many routes would you have to check on a bigger map? Picture a town whose streets make a square grid of blocks, and count the routes from one corner to the opposite corner that never pass the same corner twice (they may wander, go back west, and come round again).
| Town | Corners | Streets | Routes, corner to corner |
|---|---|---|---|
| 1 × 1 block | 4 | 4 | 2 |
| 2 × 2 blocks | 9 | 12 | 12 |
| 3 × 3 blocks | 16 | 24 | 184 |
| 4 × 4 blocks | 25 | 40 | 8,512 |
| 5 × 5 blocks | 36 | 60 | 1,262,816 |
| 6 × 6 blocks | 49 | 84 | 575,780,564 |
| 7 × 7 blocks | 64 | 112 | 789,360,053,252 |
Each block added multiplies the routes, by more each time: from 5 × 5 blocks to 6 × 6 they become over 450 times as many, and from 6 × 6 to 7 × 7 over 1,300 times. A 7 × 7 town has 112 streets and over 789 billion routes. Checking a million routes a second, a computer would take more than nine days. A real country’s road map has millions of junctions. Trying every route is hopeless.
So we need a smarter question. Here is the one that works: instead of asking about routes, ask about places. What is the quickest time from Home to each place?
The places near Home first
Look at the three trails out of Home: 9 to Bazaar, 6 to Mill, 15 to Temple.
The Mill, 6 minutes away, is the nearest. Can any other route reach the Mill in less than 6 minutes? Every route from Home starts with one of the three trails, and the other two already take 9 and 15 minutes before going anywhere. Walking on only adds minutes. So 6 is the quickest time to the Mill, for sure, without trying anything else.
Now we know the Mill is 6 minutes away, and its trails lead on: Mill to Pond is 7, so the Pond can be reached in 6 + 7 = 13; Mill to Temple is 8, so the Temple in 6 + 8 = 14, quicker than the ridge’s 15.
After the Mill, the places reached so far have these best times: Bazaar 9, Pond 13, Temple 14. Which one can we be sure of next?
Pick an answer to see why.
Nearest first
That is the whole method. Keep a best time so far beside every place you have reached. Then, again and again:
- Among the places not yet fixed, pick the one with the smallest time. Fix it: that time is now certain.
- From the place you just fixed, look along each of its trails to places not yet fixed. Its time plus the trail’s time is a new way there: if it is smaller than that place’s best so far, write it in, and remember which trail it came by.
Stop when the place you want is fixed. Then follow the remembered trails back from it to the start: that is the quickest route.
This is called Dijkstra’s algorithm, after the computer scientist who found it in 1956 (the story is below). Mathematicians call a map of places and trails with a number on each trail a weighted network: the places are vertices, the trails edges, and the numbers weights. The weight can be minutes, kilometers, rupees of bus fare, anything that adds up along a route. The question “which route has the smallest total weight?” is the shortest path problem.
Count the work. Each time a place is fixed, there is one sum for each of its trails to an unfixed place. Every trail gets its sum once, from whichever end is fixed first: 15 sums for 15 trails, against 41 routes. For the 7 × 7 town, 112 sums against 789 billion routes. Picking the smallest time each round is work too, but it grows with the number of places, not with the number of routes.
Why the smallest time is certain
Here is the map after Home, Mill and Bazaar are fixed.
Why can’t any route reach the Pond in less than 13 minutes? Think of any route from Home to the Pond. It starts inside the shaded part, and at some moment it must step out of it along one of the dashed trails. Just before it steps out, it is at a fixed place, and it has taken at least that place’s fixed time to get there, since fixed times can’t be beaten. Then it walks one dashed trail, to the Pond, the Temple or the School. The time written there is the smallest of all such ways: a fixed place’s time plus one dashed trail. So when it steps out, the route has already taken at least 13, 14 or 17 minutes, and so at least 13. After that it can only add minutes. No route reaches the Pond in less than 13, so 13 is certain.
The same argument works at every step, on any map: the smallest time outside the fixed part can never be beaten, because every other way there leaves the fixed part through a place that is already at least as far. Notice the one thing the argument needs: walking on only adds time. Keep that in mind for the twist below.
Every part of a quickest route is quickest too
The quickest route to the Mela passes the Chautari after 18 minutes, and 18 is also the quickest time to the Chautari. That is no accident. If there were a quicker way to the Chautari, say in 16 minutes, you could walk it and then carry on from the Chautari to the Mela as before, and arrive 2 minutes sooner: so the 29-minute route wouldn’t have been the quickest after all. Any part of a quickest route is itself a quickest route between its ends. That is why the remembered trails, each the last trail of a quickest way, join up into quickest routes.
Quickest, shortest or fewest?
“Best route” means nothing until you say what you are adding up. On the same roads, the route with the fewest junctions, the route with the fewest kilometers and the route with the fewest minutes can all be different. A bus route on a highway can be longer in kilometers and still quicker than a short road through a crowded bazaar. Nearest first works for any of them: just put the right number on each road.
On a map drawn to scale (Grade 7’s scale drawing) you can measure one thing for free: the straight line from start to finish, as the crow flies. No road can be shorter than the straight line between its ends, so the straight-line distance is a total no route can beat. With a top speed, it also gives a time no route can beat. A search can use this to aim at the goal instead of spreading out in every direction (it is called A* search). On real road maps, timed in minutes, this aim is weak, and route planners use better tricks: the next step after this topic.
Uphill and downhill
On a hill, a trail can take 15 minutes down and 35 minutes back up. Then a network needs one-way weights: one number for each direction. Nearest first works on one-way weights just as well, as long as each step follows a trail in the direction you would walk it. The quickest way to school and the quickest way home can then be different routes (question c).
Where nearest first goes wrong
The argument for nearest first needed one thing: walking on only adds. What if some step could take something away?
In a board game, each one-way path costs coins to walk, but one path, from B to A, has a treasure on it that pays you 4 coins. Write that as a cost of −4. What is the cheapest way from Start to Goal?
Nearest first fixes A at 2 (cheaper than B’s 5), which gives the Goal 2 + 4 = 6. Next it fixes B at 5, but B’s path to A comes too late: A is already fixed. Then it fixes the Goal at 6. But Start, B, A, Goal costs 5 − 4 + 4 = 5 coins, cheaper than 6. Nearest first gave the wrong answer, and gave no warning.
Where this is used
Questions
★ On the valley map, Home, Mill, Bazaar and Pond are fixed. The times so far are Temple 14, School 17 and Chautari 18. Which place is fixed next, and at what time?
Pick an answer to see why.
On the valley map, what are the quickest times from Home to the Temple, and by which routes? Why does nearest first give the Temple only one time?
Answer
Use nearest first on the network of Figure 26.4 to find the quickest route from A to F. Write the order in which the places are fixed, with their times.
Hint
Answer
In Figure 26.5, each trail has two times, one for each direction (the arrows). What is the quickest way from the Village to the School, and the quickest way back? Why are they different?
Answer
On the valley map, a landslide closes the short trail between the Bridge and the Chautari. What is the quickest route to the Mela now? Which places’ quickest times change?
Answer
On the way to the Mela, you must pick up a friend at the Bazaar. What is the quickest route now?
Hint
Answer
On a map at a scale of 1 : 50,000, the straight line between two villages measures 7 cm. You walk at most 5 km an hour. Can any trail get you there in under 40 minutes?
Answer
Explain why, when every time is more than zero, the quickest route never passes the same place twice.
Answer
★★★ In the coin game of Figure 26.2, suppose the treasure path pays only 1 coin instead of 4 (cost −1). Does nearest first now give the right answer?
Pick an answer to see why.
Where to go next
- Can You Cross Every Bridge Just Once? Networks without weights: a walk along every edge, and Euler’s rule for when it exists.
- How Many Ways Can You Walk to School? Counting the shortest routes on a grid of lanes, when every block takes the same time.
- What Is the Shortest Way to the River and Back? The shortest path in open country, with no roads: a mirror finds it.
- How Does a Map App Find the Quickest Route? (Grades 9–12) Searching towards the goal with the straight-line distance, and the shortcuts that make it quick on a whole country.
- How Do You Connect Every Village with the Least Cable? (Grades 9–12) Dijkstra’s other method from the same 1959 paper.
- Can a Robot Get Out of Any Maze? (Computing, Going Further 6–8) A maze is a network too.
- How a map app finds a route (Grade 10 Computing) Networks in Python, the fewest steps, and nearest first. Grade 12 Computing writes Dijkstra’s algorithm as a program in Algorithms for Hard Problems.
Where these facts come from
- Dijkstra’s own account: the ARMAC demonstration in 1956, the 64 cities and 6 bits, Rotterdam to Groningen, the café terrace with his fiancée, about twenty minutes without pencil and paper, Bauer’s request for articles and publication in 1959 (Numerische Mathematik 1, 269–271), “hardly considered mathematics”, “Das Dijkstra’sche Verfahren” in a German book on management science in the early 1960s, its use in travel planners and “you used my algorithm this morning”: Philip L. Frana, oral history interview with Edsger W. Dijkstra, Austin, Texas, 2 August 2001, Charles Babbage Institute (OH 330), transcript read October 2026.
- Dijkstra’s dates (11 May 1930 – 6 August 2002), the Mathematical Center, and the Turing Award of 1972: Wikipedia, “Edsger W. Dijkstra”, read October 2026.
- Minty’s string model (1957, an “analog computer”: knots for cities, string lengths for distances, pull the ends apart; pick the model up by the starting knot), the methods found at about the same time (Leyzorek and colleagues at the Case Institute of Technology, 1957, for the Army Electronic Proving Ground, much like Dijkstra’s; Moore at Bell Laboratories, for telephone traffic), and that nearest first needs weights that aren’t negative: A. Schrijver, “On the History of the Shortest Path Problem”, Documenta Mathematica, Extra Volume ISMP (2012) 155–167, read October 2026.
- The road network of Western Europe (18.0 million junctions), plain Dijkstra’s 9,326,696 junctions scanned and 2.2 seconds against contraction hierarchies’ 280 and 110 microseconds, companies’ secrecy, OSRM using contraction hierarchies, A* with a straight-line bound performing poorly on road maps: H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner and R. F. Werneck, “Route Planning in Transportation Networks”, arXiv:1504.05140 (2015), Table 1 and section 5, read October 2026.
- OSPF routers computing their routes with the Dijkstra algorithm, and every interface’s cost greater than zero: J. Moy, RFC 2328, “OSPF Version 2”, April 1998, read October 2026.
- Dijkstra’s algorithm used by the link-state routing protocols OSPF and IS-IS: Wikipedia, “Dijkstra’s algorithm”, read October 2026.
- The number of routes across a grid town that never pass a corner twice (2, 12, 184, 8,512, 1,262,816, 575,780,564, 789,360,053,252): OEIS A007764, read October 2026; the first five checked by our own program.
- Every other number in the topic (the 41 routes and their times, the order nearest first fixes the places, the questions’ answers, the coin game, the scale question) was computed by a program of our own.