Computer Networks · TEE · read
Dijkstra · complete example 1
Routing: build the shortest path one step at a time
TEE · shared foundations and Units 3–4 · current syllabus 702AI0C023
Practice question. Use Dijkstra’s algorithm to find the shortest path from A to D in the directed graph defined below. Show every selection, relaxation and distance table. [3 practice marks]
Answer
Given
| Edge | Cost |
|---|---|
| A→B | 4 |
| A→C | 2 |
| C→B | 1 |
| B→D | 3 |
| C→D | 7 |
Source=A; target=D. Edges are directed; do not add reverse edges.
To find
The path A to D, its total cost and intermediate work.
Formula and why
![d[v]\leftarrow\min(d[v],d[u]+w(u,v))](https://deep-learning-study-room.vercel.app/cn/math/651d18e4e3d7619d.svg)
LaTeX: d[v]\leftarrow\min(d[v],d[u]+w(u,v))Use Dijkstra because all weights are nonnegative. Select the smallest unsettled total distance, not the cheapest isolated edge.
Step-by-step solution
Step 1. Initialize
d[A]=0; every other distance=∞. No predecessors are known.
| Vertex | Distance from A | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Tentative |
| B | ∞ | — | Tentative |
| C | ∞ | — | Tentative |
| D | ∞ | — | Tentative |
Step 2. Settle A at distance 0
Unsettled candidates before selection: A=0, B=∞, C=∞, D=∞. Select the minimum; ties use alphabetical order.
| Edge | Old distance | Candidate | Decision |
|---|---|---|---|
| A→B | ∞ | 0+(4)=4 | Improve to 4; predecessor=A |
| A→C | ∞ | 0+(2)=2 | Improve to 2; predecessor=A |
| Vertex | Distance from A | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Settled |
| B | 4 | A | Tentative |
| C | 2 | A | Tentative |
| D | ∞ | — | Tentative |
Step 3. Settle C at distance 2
Unsettled candidates before selection: B=4, C=2, D=∞. Select the minimum; ties use alphabetical order.
| Edge | Old distance | Candidate | Decision |
|---|---|---|---|
| C→B | 4 | 2+(1)=3 | Improve to 3; predecessor=C |
| C→D | ∞ | 2+(7)=9 | Improve to 9; predecessor=C |
| Vertex | Distance from A | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Settled |
| B | 3 | C | Tentative |
| C | 2 | A | Settled |
| D | 9 | C | Tentative |
Step 4. Settle B at distance 3
Unsettled candidates before selection: B=3, D=9. Select the minimum; ties use alphabetical order.
| Edge | Old distance | Candidate | Decision |
|---|---|---|---|
| B→D | 9 | 3+(3)=6 | Improve to 6; predecessor=B |
| Vertex | Distance from A | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Settled |
| B | 3 | C | Settled |
| C | 2 | A | Settled |
| D | 6 | B | Tentative |
Step 5. Settle D at distance 6
Unsettled candidates before selection: D=6. Select the minimum; ties use alphabetical order.
No outgoing edges to relax.
| Vertex | Distance from A | Predecessor | State |
|---|---|---|---|
| A | 0 | — | Settled |
| B | 3 | C | Settled |
| C | 2 | A | Settled |
| D | 6 | B | Settled |
Step 6. Recover the path
Trace backwards: D ← B ← C ← A. Reverse it: A → C → B → D.
Edge sum: 2 + 1 + 3 = 6.
Final answer: A → C → B → D; cost=6.