# Q7(a) · Bellman-Ford directed graph

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2023-final/q7a

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2023-final--q7a/

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 ↔

![bellman 2023 original question graph](https://deep-learning-study-room.vercel.app/cn/fig/old-bellman-2023.5222c69942.svg)

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



$$
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.