Loading...
Dijkstra’s algorithm settles the nearest unsettled vertex using tentative route costs. Keep those costs distinct from the direct edge weights in the original graph.
What you'll be able to do
Set the start distance to zero and other distances to infinity or an explicit unknown marker. Select the unsettled vertex with the smallest tentative distance. Its current distance becomes settled under the algorithm’s non-negative-edge assumption.
The next vertex is chosen by total route cost from the start, not by the smallest edge leaving the most recently processed vertex. Specify a consistent tie rule if the trace requires one, while recognising that equal-cost alternatives can produce different valid predecessor trees.
For each suitable neighbour v of the selected vertex u, compare its old tentative distance with distance[u]+weight(u,v). If the new route is smaller, replace the distance and record u as predecessor. The predecessor identifies how the best-known route reaches v.
Repeat selection and relaxation. Reconstruct a route by following predecessors backwards from the destination and reversing the sequence. A settled-distance list is not itself the route because some settled vertices may lie on other branches.
Negative edges can invalidate the greedy settlement argument; use another suitable method when those edges are permitted. If no unsettled vertex has a finite distance, remaining vertices are unreachable from the start. For one target, its settled distance is sufficient under the usual assumptions.
AQA requires understanding and tracing the algorithm; it does not require recall of its steps from memory. Practise applying the supplied procedure accurately, including edge directions and updated distances. Real route choices may need further constraints beyond a simple weighted graph, so state what the weights and allowed routes represent.
| Settled vertex | B tentative | C tentative | D tentative |
|---|---|---|---|
| A, distance 0 | 4 | 1 | ∞ |
| C, distance 1 | 3 | 1 | 6 |
| B, distance 3 | 3 | 1 | 4 |
| D, distance 4 | 3 | 1 | 4 |
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Common mistakes to avoid
Key takeaways
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.