Floyd's algorithm
Studying this course? Keep your progress in one place.
Key facts
- Floyd's algorithm finds the shortest distance between every pair of vertices.
- It uses a distance table and a route table, each with a row and column per vertex.
- Iteration uses the th vertex as the pivot and tests every other pair.
- Update only if , and copy the route entry from .
- A network with vertices needs exactly iterations.
What Floyd's algorithm does
The distance table holds the shortest known distances and the route table holds the first vertex to travel to.
The distance table has 0 on the leading diagonal. Each other entry is the direct road length, or if there is none.
The route table entry in row , column is the first vertex to go to when travelling from to . At the start each entry is the column vertex .
For an undirected network the distance table is symmetric. For a directed network it need not be.
Distance table
- Diagonal is 0
- Direct length, or
- Updated with shorter totals
Route table
- Entry is a first vertex
- Starts as the column vertex
- Copied from
In the initial route table, what is the entry in row , column ?
One iteration
Take the next vertex as pivot and, for every other pair, check whether going through is strictly shorter.
Iteration uses the th row and column. For every pair , (neither being the pivot ), compare with going through :
If true, replace by the sum and set route entry equal to route entry . Otherwise change nothing.
The pivot's own row and column never change in its iteration. Treat as larger than any number.
- 1
Pick the pivot
the kth vertex for iteration k
- 2
Test each pair
is d(X,K) + d(K,Y) less than d(X,Y)?
- 3
Update
new distance, route entry copied from (X,K)
- 4
Otherwise
leave both tables unchanged
For a pair , and pivot : , and . What do you do?
A worked example
Each iteration tests one pivot; after all four the distance table gives every shortest distance.
Roads , , , , . Find all the shortest distances.
Update both and for an undirected network. Show each iteration with its changed entries to earn method marks.
Worked example
Apply Floyd's algorithm to the network.
- 1
Pivot : becomes (route entry ). Same for .
- 2
Pivot : becomes , route entry . : , so no change.
- 3
Pivot : becomes (route entry ). becomes (route entry ).
- 4
Pivot : no entry improves.
In the worked example, why does change from 12 to 7 in the pivot iteration?
Reading the route
Look up for the next vertex, then repeat from there until you reach . Check the lengths add to the table entry.
The distance table gives the length. To find the route from to , look up in the route table to get the next vertex . Then look up and continue until you reach .
From the worked example, : , , . The route is with length .
- 1
(B,D) = A
first move: B to A
- 2
(A,D) = C
next: A to C
- 3
(C,D) = D
last: C to D
The route table has and . What is the route from to ?
Floyd's or Dijkstra's
Floyd's gives every pair at once; Dijkstra's is quicker when only one start vertex is needed.
One run of Floyd's algorithm gives the shortest distance between every pair. Dijkstra's gives them only from one start vertex, so it would be run from each vertex in turn.
A network with vertices needs exactly iterations on an table.
For a directed network treat and separately and only use arcs that exist.
| Floyd's | Dijkstra's | |
|---|---|---|
| Finds | Every pair | One start vertex |
| Method | iterations | Labelling |
Floyd's
- Finds:
- Every pair
- Method:
- iterations
Dijkstra's
- Finds:
- One start vertex
- Method:
- Labelling
How many iterations does Floyd's algorithm need for a network with 6 vertices?
Try an exam question
A network has roads , and . Apply Floyd's algorithm, with , , as pivots in that order, to find the shortest distance from to and its route.
[4 marks]
- [1]Pivot : no entry improves, since .
- [1]Pivot : improves to (and ).
- [1]Route entry becomes , copied from .
- [1]Pivot : no change. Shortest distance by the route .
That's the notes covered.
Carry on to the next subtopic.
Try a question
After iteration 1 (pivot ), what is the entry in row , column of the distance table?
1 mark, marked against the mark scheme
After iteration 1 (pivot ), what is the entry in row , column of the distance table?
1 mark, marked against the mark scheme