Computer Networks · M2 · mocks
Q3 · Bellman–Ford shortest path
M2 mock B
Q1(a)+Q1(b) compulsory; choose any two of Q2/Q3/Q4 · 10 marks attempted
Question. Apply Bellman–Ford from A to D for directed edges A→B=5, A→C=8, B→C=−3, C→D=4, B→D=7. Show all passes using this edge order. [3 practice marks]
Answer
Given
| Directed edge | Weight |
|---|---|
| A→B | 5 |
| A→C | 8 |
| B→C | -3 |
| C→D | 4 |
| B→D | 7 |
To find
The shortest route and cost, with complete passes and a negative-cycle check.
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))Bellman–Ford permits negative edges. We use the listed order with in-place updates; do not mix this with a table that reads only the previous pass.
Diagram: Bellman–Ford · given directed graph. Labels: Bellman–Ford · given directed graph | Bellman–Ford · given directed graph | A | A | B | B | A->B | 5 | C | C | A->C | 8 | B->C | -3 | D | D | B->D | 7 | C->D | 4
Step-by-step solution
Step 1. Initialize
4 vertices → at most 3 main passes. d[A]=0; every other distance=∞. Use the listed edge order and immediate (in-place) updates.
Step 2. Pass 1: relax every edge
| Edge | Old d[target] | Candidate via source | New d[target] | Decision |
|---|---|---|---|---|
| A→B | ∞ | 0+(5)=5 | 5 | Update; predecessor=A |
| A→C | ∞ | 0+(8)=8 | 8 | Update; predecessor=A |
| B→C | 8 | 5+(-3)=2 | 2 | Update; predecessor=B |
| C→D | ∞ | 2+(4)=6 | 6 | Update; predecessor=C |
| B→D | 6 | 5+(7)=12 | 6 | No improvement |
| Vertex | A | B | C | D |
|---|---|---|---|---|
| End-of-pass distance | 0 | 5 | 2 | 6 |
| Predecessor | — | A | B | C |
Step 3. Pass 2: relax every edge
| Edge | Old d[target] | Candidate via source | New d[target] | Decision |
|---|---|---|---|---|
| A→B | 5 | 0+(5)=5 | 5 | No improvement |
| A→C | 2 | 0+(8)=8 | 2 | No improvement |
| B→C | 2 | 5+(-3)=2 | 2 | No improvement |
| C→D | 6 | 2+(4)=6 | 6 | No improvement |
| B→D | 6 | 5+(7)=12 | 6 | No improvement |
| Vertex | A | B | C | D |
|---|---|---|---|---|
| End-of-pass distance | 0 | 5 | 2 | 6 |
| Predecessor | — | A | B | C |
Step 4. Stop after an unchanged pass
This entire pass changed no distance. Further identical relaxation passes will not improve anything.
Step 5. Recover and total the path
Backward predecessors: D ← C ← B ← A. Forward route: A → B → C → D.
Cost = (5) + (-3) + (4) = 6. No edge can now improve its destination label.
Final answer: A → B → C → D; shortest cost=6.