Computer Networks · TEE · papers

Q2(a) · Dijkstra from w

2024-02-06 · AI-only Sem V variant

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

Q2(a). Using Dijkstra’s algorithm calculate shortest paths from w to all nodes in the original graph. Show all steps; the complete edge list is below. [10 marks]

Original diagram data

Edge endpoint1	Endpoint2	Cost
z	x	8
z	y	12
x	y	6
x	v	3
x	w	6
y	v	8
y	t	7
v	t	4
v	u	3
v	w	4
w	u	3
t	u	2

Answer

Given

The original diagram is undirected. All edge labels are reproduced below. Source = w.

Swipe across the diagram to read its labels ↔

Diagram: Original undirected question graph: every edge weight retained; source w. Labels: Original undirected question graph: every edge weight retained; source w | 8 | 12 | 6 | 3 | 6 | 8 | 7 | 4 | 3 | 4 | 3 | 2 | z | x | y | w | v | t | u

From	To	Cost
z	x	8
z	y	12
x	y	6
x	v	3
x	w	6
y	v	8
y	t	7
v	t	4
v	u	3
v	w	4
w	u	3
t	u	2

To find

Shortest distance, complete route and predecessor for every node from w.

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. Dijkstra settles the unvisited node of least tentative distance. Nonnegative edge costs make the settled distance final. Equal-distance nodes may be settled in either order.

Step 1. Initialize and relax

Pass / settled node	Strict improvements	t	u	v	x	y	z
0	Initial	∞	∞	∞	∞	∞	∞
w	u←w: 0+3=3; x←w: 0+6=6; v←w: 0+4=4	∞	3	4	6	∞	∞
u	t←u: 3+2=5	5	3	4	6	∞	∞
v	y←v: 4+8=12	5	3	4	6	12	∞
t	No change	5	3	4	6	12	∞
x	z←x: 6+8=14	5	3	4	6	12	14
y	No change	5	3	4	6	12	14
z	No change	5	3	4	6	12	14

Step 2. Read predecessors backwards, then reverse

Destination	Distance	Previous	Route
t	5	u	w → u → t
u	3	w	w → u
v	4	w	w → v
w	0	—	w
x	6	w	w → x
y	12	v	w → v → y
z	14	x	w → x → z

A tie between two equally short paths is valid; this table retains the first predecessor on equal distances.