Coaching Centre
Shortest paths
Finding the shortest path between two vertices of a weighted network, first by inspection and then with the labelling method (Dijkstra's algorithm).
Every time a maps app suggests a route, it is solving a shortest path problem on a network with millions of vertices. You'll do the same thing by hand on networks with up to ten. The method is the same one the apps are built on.
What "shortest" means
The length of a path in a weighted network is the sum of the weights of its edges. The shortest path between two vertices is the path with the smallest total weight. If the weights are times, it's the quickest route. If they are costs, it's the cheapest.
On a small network you can often see the answer by listing the sensible paths and adding them up. That is called finding it by inspection. It works, but it is easy to miss a route, and it gets out of hand quickly as networks grow. So we use a method that can't miss anything.
The labelling method
The labelling method is also called Dijkstra's algorithm, after the Dutch computer scientist who invented it in 1956, reportedly in about twenty minutes while sitting at a café in Amsterdam. The idea is to work outwards from the start, always settling the closest vertex you haven't settled yet. Each vertex gets a label: the shortest distance to it found so far.
- Give the start vertex the label $0$ and make it permanent (box it or circle it).
- For every neighbour of the vertex you just made permanent, work out its label + the edge weight. If that beats the neighbour's current label (or it has none), write the new number as the neighbour's temporary label.
- Of all the temporary labels, find the smallest. Make that vertex permanent.
- Repeat steps 2 and 3 until the destination is permanent. Its label is the shortest distance.
- To find the path itself, work backwards from the destination. Each time, step to the neighbour whose permanent label plus the edge weight equals the current label.
Why does it work? When a vertex has the smallest temporary label, any other way to reach it would have to pass through a vertex that is already further away. So nothing can beat that label, and it is safe to make it permanent.
Use the labelling method to find the shortest path from S to T in the network above.
Making it reliable
- Only update the neighbours of the vertex you just made permanent.
- Never change a permanent label. Once a vertex is settled, it's settled.
- If two temporary labels tie for smallest, pick either. You'll get the same answer.
- In a directed network, only follow arrows forwards.
- You can stop as soon as the destination is permanent, but finishing every vertex gives the shortest path from the start to everywhere at once.
Before using any buttons, tap roads to build your own route from Penrith to the CBD. Write down your time.
Now press Show the labelling method and step through it. Which vertex becomes permanent second, and why that one?
Press New trip and try Liverpool to Ryde. Did you beat the method or match it? The times are typical, not live traffic.
Your turn
Using the labels from Example 1, find the shortest path from S to E and its length.
Show the working
E's permanent label is $14$. Backtrack: $14 - 5 = 9$ at C, then C came from B ($9 - 3 = 6$), then A ($6 - 2 = 4$), then S. Path S–A–B–C–E, length $4 + 2 + 3 + 5 = 14$ minutes.
In the Example 1 network, what is the shortest time from S to C?
C's permanent label is $9$, via S–A–B–C: $4 + 2 + 3 = 9$.
In the same network, what is the shortest time from S to D?
D's permanent label is $13$: S–A–B–C–D $= 4 + 2 + 3 + 4 = 13$. The direct edge A–D gives $4 + 11 = 15$.
In the labelling method, which vertex is made permanent next?
The smallest temporary label is the smallest total from the start. That is what makes it safe to fix.
A vertex has temporary label $12$. Its newly permanent neighbour has label $5$ and the edge between them has weight $6$. The new temporary label is:
$5 + 6 = 11$, which beats $12$, so the label changes to $11$.
On the Example 1 network, a student always takes the shortest edge to a new vertex: S–A–B–C–D–E–T. How long is that route?
$4 + 2 + 3 + 4 + 2 + 4 = 19$. That's $3$ minutes longer than the true shortest path, which is why greedy choices aren't a method.
Which statement is true?
S–A–B–C–D–T has five edges but beats the three-edge S–A–D–T. Shortest paths can also tie, so there isn't always just one.
If the road C–D in Example 1 were closed, by how many minutes would the shortest time from S to T increase?
A, B, C and E keep their labels ($4$, $6$, $9$, $14$). D can now only be reached by A–D ($4 + 11 = 15$) or E–D ($14 + 2 = 16$), so D $= 15$. Then T via D is $15 + 3 = 18$ and T via E is $14 + 4 = 18$. The new shortest time is $18$, an increase of $18 - 16 = 2$ minutes.
Exam style: A courier must go from S to T in the Example 1 network. What is the minimum travel time in minutes?
From the labelling method, T's permanent label is $16$, via S–A–B–C–D–T.
Exam style: Using the labelling method, after S, A and B are permanent in Example 1, the temporary labels are C $9$, D $15$ and E $15$. Which vertex becomes permanent next, and why?
Always fix the smallest temporary label: C at $9$.