# Q6(c) · Recovering unknown routing weights

Subject: Computer Networks

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/cn/#tee/papers/paper-2024-ai-final/q6c

Canonical: https://deep-learning-study-room.vercel.app/read/cn/tee/papers/paper-2024-ai-final--q6c/

Exact historical variant. Current-syllabus questions solved; excluded topics and source limitations stated.

### Q6(c). Undirected graph: U–V has unknown link cost X, U–nodeX has unknown link cost Y, U–W=8, V–W=1, V–nodeX=4, nodeX–W=7, nodeX–nodeY=4, W–nodeY=1, W–Z=4, nodeY–Z=6. The shortest-path table from V is V:0/none, W:1/V, nodeY:2/W, nodeX:4/V, Z:5/W, U:6/V. Find unknown edge costs X and Y; write n/a if undetermined. [5 marks]

### Answer

### Given

dV(U)=6 with predecessorV; dV(nodeX)=4 with predecessorV. Unknown linkX is U–V; linkY is U–nodeX.

### To find

Unknown edge costs or n/a.

### Formula and why



$$
d(U)=d(\operatorname{pred}(U))+c(\operatorname{pred}(U),U)
$$



A predecessor edge lies on the reported shortest path, so its cost is fixed by the distance difference. An unused edge is usually constrained, not uniquely determined.

### Solution

### Step 1. Recover link X

U’s predecessor isV:6=0+X, therefore **X=6**.

### Step 2. Test what is known about link Y

The alternate routeV→nodeX→U costs4+Y. It must not be shorter than6, henceY≥2 (assuming nonnegative costs). Many values satisfy this; ifY=2 there is a tie and predecessorV remains valid. Therefore **Y=n/a (not uniquely determined)**.