Given the network shown above, show the development of the routing table for node A using Dijkstra’s algorithm. You must show your work and the final routing table (next hop and path cost for each destination) for full marks.
Figure required: Figure 1 (network): nodes A, B, C, D, E with link costs A–B 2, A–C 1, B–C 2, B–D 2, D–E 3, A–E 8.
Try an answer before revealing the guidance below.
Key Concepts
- Set N′
- Tentative cost D(v)
- Predecessor p(v)
- Least-cost node
- Next hop from path
Answer Approach
- Initialise D(v) for A’s direct neighbours; others are ∞.
- Each step, add the not-yet-visited node with the least D(v) to N′.
- Update D(w) = min(D(w), D(v) + c(v, w)) for its neighbours.
- Trace predecessors back to A to find each destination’s next hop.
Full Answer
Answer status: Draft answer (unofficial). Revision notes, not an official marking scheme.
Step 0: N′ = {A}; D(B) = 2 via A, D(C) = 1 via A, D(E) = 8 via A, D(D) = ∞. Step 1: add C (1); via C, B = 1 + 2 = 3 (no improvement). Step 2: add B (2); D(D) = 2 + 2 = 4 via B. Step 3: add D (4); D(E) = min(8, 4 + 3) = 7 via D. Step 4: add E (7). Final routing table at A: B → next hop B, cost 2; C → C, cost 1; D → B, cost 4 (A–B–D); E → B, cost 7 (A–B–D–E).
D(w) = min(D(w), D(v) + c(v, w))Shortcuts: K concepts · A approach · F answer · R reviewed · B bookmark · ← / → previous / next