Floyd's algorithm 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; (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 mean?
- The first vertex to travel to when going from to .
- How many iterations does a network with vertices need?
- , 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 ?
- .
- What is the new route entry when an update is made?
- The entry : copy the first step from towards .
- 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 to get , then , and so on until you reach .
- 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.