Dijkstra'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.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What does Dijkstra's algorithm find?
- The shortest distance from a start vertex to every other vertex, labelled in order of increasing distance.
- What three things are recorded in each vertex box?
- The order of labelling, the final value and the working values.
- What is the first step of Dijkstra's algorithm?
- Give the start vertex order 1 and final value .
- How do you choose the next vertex to label permanently?
- Choose the unlabelled vertex with the smallest working value.
- How do you calculate a new working value?
- Final value of the vertex just labelled plus the arc weight to the neighbour.
- When do you replace a working value?
- Only when the new value is smaller than the one already there.
- How do you find the route after finishing?
- Back-track from the target: choose the neighbour whose final value equals this vertex's final value minus the arc weight.
- Can the shortest route use a direct arc that is longer than a two-arc route?
- No. Compare the working values: the smaller one gives the final value.
- When can Dijkstra's algorithm stop?
- When the target vertex has been permanently labelled.
- A road in the network closes. What do you do?
- Remove the arc and apply the algorithm again.
- A new arc of weight is added. When does it shorten the route from to ?
- When is less than the current shortest length.
- What must be true of the arc weights for Dijkstra's algorithm?
- They must be positive, such as distances, times or costs.