Floyd's algorithm

Floyd's algorithm Flashcards

Spec 2.2 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

13 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 13 cards
What does Floyd's algorithm find?
The shortest distance between every pair of vertices.
What are the two tables in Floyd's algorithm?
A distance table and a route table.
What is in the distance table at the start?
0 on the leading diagonal; direct road lengths; ∞\infty (a dash) where there is no direct road.
What is in the route table at the start?
In each entry, the column vertex.
What does a route table entry (X,Y)(X,Y) mean?
The first vertex to travel to when going from XX to YY.
How many iterations does a network with nn vertices need?
nn, one per pivot vertex.
Which row and column does iteration 1 use?
The first row and first column.
What is the update test in iteration KK?
d(X,K)+d(K,Y)<d(X,Y)d(X,K)+d(K,Y)<d(X,Y).
What is the new route entry when an update is made?
The entry (X,K)(X,K): copy the first step from XX towards KK.
What if the new total equals the current value?
Leave the entries unchanged: update only if strictly less.
How do you read off a route?
Look up (X,Y)(X,Y) to get ZZ, then (Z,Y)(Z,Y), and so on until you reach YY.
Does the pivot's row or column change in its own iteration?
No.
When is Floyd's algorithm better than Dijkstra's?
When shortest distances between every pair are needed.

Flashcards