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 path from a start vertex to the other vertices of a network with non-negative weights.
- What is stored in each vertex box?
- Vertex, order of labelling, final label and working values.
- What is a working value?
- A temporary distance at a vertex that is replaced if a smaller one is found.
- What is the label of the start vertex?
- 0, with order of labelling 1.
- How is the next permanent label chosen?
- The smallest working value among all vertices not yet permanently labelled.
- What do you do if a new route to a vertex is shorter?
- Replace the working value with the smaller one and cross out the old.
- When does the algorithm stop for one target?
- When the target receives a permanent label.
- How do you find the route after labelling?
- Work back from the target: choose the neighbour whose label plus edge length equals the current label.
- Why is the smallest working value final?
- Any other route goes through a vertex with a larger working value, and weights are not negative.
- How do you find the shortest route through a given vertex ?
- Add the shortest distance from start to and the shortest distance from to the target.
- What happens to labels when a road closes?
- Labels of vertices whose routes do not use the closed road are unchanged; recalculate from where it mattered.
- In a directed network, which edges are used?
- Only arcs followed in the direction of their arrows.