Computer Networks · TEE · papers

Q4(a) · Dijkstra from u

2023-11-22 · AI-only Sem V variant; incomplete recovered scan

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

Q4(a). Using Dijkstra’s algorithm, calculate the shortest path from u to all nodes in the given undirected graph. Show every step. The complete original edge list is reproduced 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 = u.

Swipe across the diagram to read its labels ↔

Diagram: Original undirected question graph: every edge weight retained; source u. Labels: Original undirected question graph: every edge weight retained; source u | 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 u.

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	v	w	x	y	z
0	Initial	∞	∞	∞	∞	∞	∞
u	v←u: 0+3=3; w←u: 0+3=3; t←u: 0+2=2	2	3	3	∞	∞	∞
t	y←t: 2+7=9	2	3	3	∞	9	∞
v	x←v: 3+3=6	2	3	3	6	9	∞
w	No change	2	3	3	6	9	∞
x	z←x: 6+8=14	2	3	3	6	9	14
y	No change	2	3	3	6	9	14
z	No change	2	3	3	6	9	14

Step 2. Read predecessors backwards, then reverse

Destination	Distance	Previous	Route
t	2	u	u → t
u	0	—	u
v	3	u	u → v
w	3	u	u → w
x	6	v	u → v → x
y	9	t	u → t → y
z	14	x	u → v → x → z

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