Computer Networks · TEE · papers
Q7(a) · Bellman-Ford directed graph
2023-11-22 · Final 2023-24 / Re-exam 2022-23
Actual paper; 100 marks attempted. Current-syllabus alignment is stated per question.
Q7(a). Consider the directed graph with costs given below. Determine the shortest path from source vertex A to every other vertex in the graph using Bellman Ford Algorithm. Illustrate step-by-step procedure and draw the shortest path table. [10 marks]
Original diagram data
| From | To | Cost |
|---|---|---|
| A | B | 4 |
| A | C | 3 |
| A | D | 6 |
| C | B | -1 |
| D | C | -4 |
| B | E | -1 |
| C | E | 2 |
| D | F | -2 |
| E | F | 3 |
Answer
Given
The original diagram is directed. All edge labels are reproduced below. Source = A.
Swipe across the diagram to read its labels ↔
Diagram: bellman 2023 original question graph. Labels: bellman 2023 original question graph | 4 | 3 | 6 | -1 | -4 | -1 | 2 | -2 | 3 | A | B | C | D | E | F
| From | To | Cost |
|---|---|---|
| A | B | 4 |
| A | C | 3 |
| A | D | 6 |
| C | B | -1 |
| D | C | -4 |
| B | E | -1 |
| C | E | 2 |
| D | F | -2 |
| E | F | 3 |
To find
Shortest distance, complete route and predecessor for every node from A.
Formula and why
LaTeX: d(v)\leftarrow\min(d(v),d(u)+w(u,v))Relaxation replaces a tentative route when going through u is cheaper. Bellman–Ford permits negative edge weights. This table uses synchronous passes: pass k uses distances at the end of pass k−1, so it covers paths of at most k edges.
Step 1. Initialize and relax
| Pass / settled node | Strict improvements | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 0 | Initial | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1 | B←A: 0+(4)=4; C←A: 0+(3)=3; D←A: 0+(6)=6 | 0 | 4 | 3 | 6 | ∞ | ∞ |
| 2 | B←C: 3+(-1)=2; C←D: 6+(-4)=2; E←B: 4+(-1)=3; F←D: 6+(-2)=4 | 0 | 2 | 2 | 6 | 3 | 4 |
| 3 | B←C: 2+(-1)=1; E←B: 2+(-1)=1 | 0 | 1 | 2 | 6 | 1 | 4 |
| 4 | E←B: 1+(-1)=0 | 0 | 1 | 2 | 6 | 0 | 4 |
| 5 | F←E: 0+(3)=3 | 0 | 1 | 2 | 6 | 0 | 3 |
Step 2. Read predecessors backwards, then reverse
| Destination | Distance | Previous | Route |
|---|---|---|---|
| A | 0 | — | A |
| B | 1 | C | A → D → C → B |
| C | 2 | D | A → D → C |
| D | 6 | A | A → D |
| E | 0 | B | A → D → C → B → E |
| F | 3 | E | A → D → C → B → E → F |
Step 3. Check for a reachable negative cycle
| Edge | Candidate d[u] + weight | Current d[v] | Improvement? |
|---|---|---|---|
| A → B | 0 + (4) = 4 | 1 | No |
| A → C | 0 + (3) = 3 | 2 | No |
| A → D | 0 + (6) = 6 | 6 | No |
| C → B | 2 + (-1) = 1 | 1 | No |
| D → C | 6 + (-4) = 2 | 2 | No |
| B → E | 1 + (-1) = 0 | 0 | No |
| C → E | 2 + (2) = 4 | 0 | No |
| D → F | 6 + (-2) = 4 | 3 | No |
| E → F | 0 + (3) = 3 | 3 | No |
No edge improves its destination on the extra pass. Therefore no negative cycle reachable from the source is detected.