Shortest Paths
Finding the best path from A to B
What's the shortest way to get from Auckland to Wellington? If we know all the distances between the towns and cities along the way, then we can find all the different routes to take from Auckland and Wellington, and choose the shortest.
Best Guess
Finding the total length of three or more promising looking routes through a network is often enough to find the shortest path.
Applying common sense and making reasonable assumptions can mean not too many routes need to be checked.
However, this doesn't always work, especially if a network is large or complicated. A more systematic approach will always be better.
The network of roads between Auckland and Wellington has three likely routes.
A-H-NE-P-W is total length 737km.
A-H-T-NA-P-W is total length 740km.
A-H-T-P-W is total length 661km. This is the shortest route.
Animated Shortest Path
The animation shows a board game, where the player starts in the top-left corner. We want to know what the shortest path is from there to the bottom right corner.
Each frame of the animation moves one place further through the board game.
After 15 steps, the leading edge of the possible positions reaches the goal point; it is 15 steps from the top left to the bottom right.
Dijkstra's Algorithm
There is an algorithm which pretty much replicates what is happening in the board game above. Named after renowned Dutch computer scientist Edsger Dijkstra, it was first described in 1956.
The algorithm is a bit more complicated that those for MST's, but it still repeats a same process in a loop until the shortest path is found.
Step 1: Label the start node with a distance 0. All the other nodes are blank.
Step 2: Choose X, a labelled node that has not yet been chosen as X, having the smallest distance label. This is sometimes called the active node.
Step 3: Calculate new distances for each of the neighbours of X (add the edge weights to the label of X).
Step 4: If these distances are an improvement (smaller), change the labels.
Step 5: If the finish node was X, stop. Otherwise, return to Step 2.
The label at the finish node is the weight of the shortest path from start to finish.
If Dijkstra's algorithm runs until every node takes a turn as X, then it generates the shortest path from the start node to every other node.
This is a worked example of Dijkstra's algorithm.
Dijkstra.pdfCheckpoint
For the network shown:
- What is the shortest path from A to E?
- What is the shortest path from C to E?
- What is the shortest path from B to E?
- Find three paths from A to G, and their lengths.
- Find the shortest path from A to G (using any method).
- Dijkstra's algorithm is applied with start node A. After A, which node becomes the active node ("X")?
Exercises
Use a copy of the exercise sheet and draw each network, then find a shortest path from A to Z.
Exercise.pdfExercise 4x.pdfTasks
100 Acre Wood
Task 4: Winnie-the-Pooh wants to visit Christopher Robin for lunch. He also wants to stop by Rabbit's house when returning, on the off chance that he is offered a second lunch. Plan his trip, there and back.
100acre.pdfSherwood Forest
Task 4:Robin Hood is camped in Derby, and needs to meet Maid Marion halfway between Wakefield and Pontefract. What is the best way for him to get there?
sherwood.pdfThe Shire
Task 4: Sam is at Weathertop, and needs to get to the Grey Havens. He expects that the shortest route will cross the Brandywine Bridge.
What is the shortest route that he can take, and how much longer would it take if he wanted to avoid crossing the Brandywine Bridge?
shire.pdfInvestigations
(A) How could you best use Dijkstra's algorithm to find the shortest path from A to B that passes through C?
(B) If d(A,B) denotes the distance between A and B in a network, explain why d(X,Y) + d(Y,Z) ≤ d(X,Z).
If you have worked through the sections in order, and completed the tasks and investigations, then you are ready to complete the practice assessment.
Also, 6:Extended is a deeper overview of possible problems requiring extended abstract thinking.
practice.pdfKeywords: path, shortest path, Dijkstra's algorithm, active node