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.
COMMON MISCONCEPTION
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 in the network becomes permanent, and then its neighbours are updated.
Notice where that choice is made. It is across the whole network, not among the edges leaving the node you happen to be at. A greedy walk that always takes the cheapest next edge 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. Be careful what the label test proves. An edge UV whose weight equals the difference of its two final labels lies on some shortest path from the start to whichever end carries the larger label, and that is the whole of the claim. It is no test for membership of the route you were asked for: in the network below AB has weight 5 and B's label is 5, so AB passes it, and the route to F never goes near B.
So backtrack rather than collect. From the destination, find a neighbour whose label plus the connecting edge's weight equals the destination's label, step to it, and repeat until you reach the start. It is the same arithmetic, but applied only at the vertex you are standing on, and that is what chains the edges into one path. If two neighbours pass at the same vertex there are two shortest routes of equal length; say so, and give both when the question asks for all of them.
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.
Two other edges pass the same difference test and belong to no part of this answer: AB, since 5 − 0 = 5, and AD, since 9 − 0 = 9. Both are on shortest routes, to B and to D respectively. Collecting every matching edge would have produced a set with branches in it rather than a route, which is why the backtrack starts at F and follows one predecessor at a time.
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 improves on the entry already recorded. When it does, the distance is replaced, and the route entry for that cell is replaced by the entry sitting in the same row of column k. That entry is the first node to head for, so reading a route means hopping from cell to cell.
The convention on this paper is to run the first iteration on the first row and column, the second on the second, and so on until every node has served as an intermediate. The result is the shortest distance between every pair, which Dijkstra would need one run per starting node to produce.
GUIDED PRACTICE
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 improves on having no route at all, the distance entry becomes 13.
The route entry for A to E is replaced by whatever sits in row A of column C. Here A joins C directly, so that entry is C, the first node to head for.
The matrix is symmetric here, so the entry from E to A changes to 13 as well, with route C.
ASSESSMENT FOCUS
- 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.
- Backtrack from the destination, testing each edge at the vertex you are standing on, rather than guessing the route from the picture. Difference-matching on its own also flags edges on shortest routes to other vertices, so it is not a route by itself.
- Where two edges into the same vertex both match, there are two shortest routes of equal length. Say so, and give both if the question asks for all of them.
- For Floyd, say which node the iteration is using and update both matrices together.
- In Floyd, copy the row and column of the iteration node down unchanged; only the other cells can improve.
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
11 − 9 = 2, which equals the weight of RS, so yes: RS lies on a shortest route to S, and the backtrack continues from R. Had the question named a destination beyond S, the same match would have settled nothing, since it speaks only about routes to S.
Dijkstra makes permanent the smallest temporary label anywhere in the network, not the cheapest edge from where you are.
Backtrack from the destination through matching labels, since the match alone only names an edge on some shortest route; 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.
Or read them with their worked answers on the shortest paths: dijkstra and floyd questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- 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.