Maths › Decision Mathematics 1 › Shortest paths: Dijkstra and Floyd
Shortest paths: Dijkstra and Floyd
The cheapest route from one node to another, found by labelling nodes in the order they are settled. A second algorithm does every pair at once, at the cost of a good deal more bookkeeping.
Builds on Minimum spanning trees: Prim and Kruskal and Graphs: order, Eulerian paths and planarity.
IN THIS TOPIC
- Apply Dijkstra's algorithm with the standard boxed labels.
- Read the shortest route back by working from the destination.
- Carry out an iteration of Floyd's algorithm on a distance and a route matrix.
WHAT YOU PROBABLY THINK
Dijkstra's algorithm finds the shortest route by choosing the smallest edge at each node along the way.
Labelling in order of distance
Each node carries a box with three entries: the order in which it was permanently labelled, its final distance from the start, and the working values that were tried along the way. At each step the smallest temporary label anywhere becomes permanent, and then its neighbours are updated.
The key point is that the choice is made across the whole network, not among the edges leaving the current node. A greedy walk that always takes the cheapest next edge, as the opening claim describes, can be led badly astray by one short edge into an expensive corner.
To read the route back, start at the destination and work backwards: an edge lies on the shortest path exactly when the difference of the two final labels equals its weight.
WORKED EXAMPLE
Shortest route from A to F
Apply Dijkstra to the network to find the shortest route from A to F.
Final labels: A 0, B 5, C 7, D 9, E 13, F 15.
Working back from F: 15 − 13 = 2, the weight of EF, so EF is on the route. Then 13 − 7 = 6 = CE, and 7 − 0 = 7 = AC.
The route is A, C, E, F of length 15. The apparently direct A, D, F comes to 19.
Every pair at once
Floyd's algorithm keeps two tables: a distance matrix and a route matrix. Iteration k asks, for every pair of nodes, whether going via node k is shorter than the entry already recorded. If it is, the distance is replaced and the route entry is changed to the first step towards k.
The convention on this paper is to do the first iteration on the first row and column, the second on the second, and so on until every node has been used as an intermediate. The result is the shortest distance between every pair, which Dijkstra would need one run per starting node to produce.
YOUR TURN
One Floyd iteration
In a distance matrix the entry from A to E is currently unreachable, the entry from A to C is 7 and from C to E is 6. Describe what the C iteration does and what the route matrix records.
Show the working
The iteration compares the current A to E entry with the sum of A to C and C to E, which is 7 + 6 = 13.
Since 13 beats no route at all, the distance entry becomes 13.
The route entry for A to E is changed to C: the first node to head for on the way.
The matrix is symmetric here, so the entry from E to A changes to 13 as well, with route C.
THE EXAM BIT
- Draw the three-part boxes and fill in every working value, crossed out as it is beaten.
- Number the order of permanent labelling; it carries marks on its own.
- Read the route back by differencing final labels, not by guessing from the picture.
- For Floyd, say which node the iteration is using and update both matrices together.
CHECK YOURSELF
In a Dijkstra solution the final labels are P 0, Q 4, R 9 and S 11, and the edge RS has weight 2. Is RS on the shortest route to S?
Show a hint
Difference the labels.
Show the answer
1
1
−
9
=
2
,
w
h
i
c
h
e
q
u
a
l
s
t
h
e
w
e
i
g
h
t
o
f
R
S
,
s
o
y
e
s
:
R
S
l
i
e
s
o
n
a
s
h
o
r
t
e
s
t
r
o
u
t
e
t
o
S
.
Dijkstra makes permanent the smallest temporary label anywhere in the network, not the cheapest edge from where you are.
Read the route back by differencing final labels; Floyd instead does every pair at once, one intermediate node per iteration.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Apply Dijkstra's algorithm with the standard boxed labels.
- Read the shortest route back by working from the destination.
- Carry out an iteration of Floyd's algorithm on a distance and a route matrix.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.