Dijkstra's algorithm
Shortest paths from a source in a graph with positive weights: the table of tentative distances and predecessors, picking the closest vertex, updating its neighbours, reading the path back, the failure with a negative weight and the cost with a priority queue.
- 26 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Tentative distance: what is it?
Show the answer
The length of the best path found so far from the source to a vertex, a value that can still drop until that vertex is fixed.
At the start it is 0 for the source and infinity for every other vertex. Once the vertex is fixed, it becomes its true distance and never changes again.
In this undirected graph, A is the source. After fixing A (distance 0), which vertex does Dijkstra's algorithm fix next?
```text
A - B : 4
A - C : 2
B - C : 1
B - D : 5
C - D : 8
C - E : 10
D - E : 2
D - F : 6
E - F : 3`- C, with tentative distance 2
- B, with tentative distance 4
- D, neighbour of B and C
- B, A's first neighbour in alphabetical order
Show the answer
C, with tentative distance 2
After A, the tentative distances are B = 4 and C = 2; the others are infinity. The smallest is fixed, C. Alphabetical order plays no part in Dijkstra, only distance matters.
At each round, Dijkstra's algorithm … the unfixed vertex whose tentative distance is the …, then updates its neighbours.
Show the answer
At each round, Dijkstra's algorithm fixes the unfixed vertex whose tentative distance is the smallest, then updates its neighbours.
It is a greedy choice: we never come back to that vertex. It is correct because no weight is negative.
Fixed vertex: what is it?
Show the answer
A vertex whose distance from the source is final: the algorithm has proved that no other path can be shorter.
At each round, the unfixed vertex with the smallest tentative distance is fixed. Any other path to it would go through a vertex at least as far, and positive weights cannot shorten it.