4.3.6.1 - Dijkstra's shortest-path algorithm (Python)
Learn to apply a supplied shortest-path algorithm, trace tentative distances and predecessor changes, and interpret the route found in a weighted graph.
Tentative distances and visited nodes
Dijkstra's algorithm finds least-total-weight routes from a start vertex when all edge weights are non-negative.
Tentative distance
The cost of the best route found so far to a vertex; it can decrease while better routes are being discovered.
The start has distance 0; every other vertex starts at infinity, meaning no route has yet been found. A settled vertex has had its shortest distance finalised. Some descriptions call settled vertices “visited”; distinguish this from merely having a finite tentative distance.
For this lesson, use these supplied steps:
- Set the start's distance to 0 and all others to infinity. Set predecessors to none and all vertices unsettled.
- Select the unsettled vertex with smallest tentative distance. Break ties alphabetically.
- If its distance is infinity, stop: all remaining vertices are unreachable. Otherwise settle it.
- For each unsettled neighbour, add this vertex's distance to their edge weight. If the sum is smaller than the neighbour's distance, replace that distance and record this vertex as predecessor.
- Repeat until no unsettled vertices remain. To find only one target, stopping when that target is settled is safe.
You are expected to understand and trace Dijkstra's algorithm, not recall its steps from memory. Any task asking you to apply or amend it supplies the steps or source.
A cheaper route to an unsettled vertex can still be found. Settling the smallest-distance vertex is safe because, with non-negative weights, going through another unsettled vertex cannot produce a cheaper route back to it. Negative weights break this justification; do not apply the given algorithm to them.
Relaxing weighted edges
Relaxing an edge means checking whether going through the current vertex improves the best known distance to its neighbour.
Use this undirected graph; weights are journey times in minutes. Unlisted edges do not exist.
| Edge | Weight |
|---|---|
| A–B | 4 |
| A–C | 1 |
| C–B | 2 |
| B–D | 1 |
| C–D | 5 |
| D–E | 3 |
| B–E | 7 |
[DIAGRAM: asset_slug: py_dijkstra_graph; description: Exact weighted graph showing the seven supplied non-negative journey times.]
Start at A. Each row records distances after settling the named vertex and relaxing its neighbours; a dash means no predecessor.
| Settled now | A | B | C | D | E | Changed predecessors |
|---|---|---|---|---|---|---|
| initial | 0 | ∞ | ∞ | ∞ | ∞ | all — |
| A | 0 | 4 | 1 | ∞ | ∞ | B←A, C←A |
| C | 0 | 3 | 1 | 6 | ∞ | B←C, D←C |
| B | 0 | 3 | 1 | 4 | 10 | D←B, E←B |
| D | 0 | 3 | 1 | 4 | 7 | E←D |
| E | 0 | 3 | 1 | 4 | 7 | none |
The C–B relaxation computes 1 + 2 = 3, replacing 4; the B–D relaxation computes 3 + 1 = 4, replacing 6. A predecessor changes whenever the corresponding tentative distance improves. Using only an edge weight, instead of the accumulated distance plus that weight, would confuse a local edge with a whole route.
See a route improve
{"code":"def dijkstra(graph, start):\n distances = {v: float('inf') for v in graph}\n previous = {v: None for v in graph}\n unsettled = set(graph)\n distances[start] = 0\n while unsettled:\n current = min(unsettled, key=lambda v: (distances[v], v))\n if distances[current] == float('inf'):\n break\n unsettled.remove(current)\n for neighbour, weight in graph[current].items():\n if neighbour in unsettled:\n candidate = distances[current] + weight\n if candidate < distances[neighbour]:\n distances[neighbour] = candidate\n previous[neighbour] = current\n print(current, distances)\n return distances, previous\n\ngraph = {'A': {'B': 4, 'C': 1}, 'B': {'A': 4, 'C': 2, 'D': 1, 'E': 7}, 'C': {'A': 1, 'B': 2, 'D': 5}, 'D': {'B': 1, 'C': 5, 'E': 3}, 'E': {'B': 7, 'D': 3}}\ndistances, previous = dijkstra(graph, 'A')\nprint('Predecessors:', previous)","instructions":"Predict the settle order and final distance to E, then Run. Change the B–E weight from 7 to 2 in both adjacency entries. Predict/run again: does the predecessor of E still change when D is settled?","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
The implementation uses an adjacency dictionary of dictionaries and chooses the next vertex by scanning unsettled vertices. It is a clear small-graph implementation; tracing it does not require learning a priority-queue implementation. It assumes all neighbour labels are dictionary keys and all weights meet the non-negative condition.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account