Computer Networks · TEE · papers

Q3(a) · Dijkstra from u

2023-01-27 · AI-only Sem V

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

Q3(a). Using Dijkstra’s algorithm calculate shortest paths from u to all nodes, showing every step. The original undirected graph’s edges are reproduced below. [10 marks]

Original diagram data

Edge endpoint1	Endpoint2	Cost
u	v	4
u	w	3
u	x	5
v	w	1
v	x	8
x	w	7
x	y	7
w	y	6
w	z	7
y	z	7

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 | 4 | 3 | 5 | 1 | 8 | 7 | 7 | 6 | 7 | 7 | u | v | x | w | y | z

From	To	Cost
u	v	4
u	w	3
u	x	5
v	w	1
v	x	8
x	w	7
x	y	7
w	y	6
w	z	7
y	z	7

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	v	w	x	y	z
0	Initial	∞	∞	∞	∞	∞
u	v←u: 0+4=4; w←u: 0+3=3; x←u: 0+5=5	4	3	5	∞	∞
w	y←w: 3+6=9; z←w: 3+7=10	4	3	5	9	10
v	No change	4	3	5	9	10
x	No change	4	3	5	9	10
y	No change	4	3	5	9	10
z	No change	4	3	5	9	10

Step 2. Read predecessors backwards, then reverse

Destination	Distance	Previous	Route
u	0	—	u
v	4	u	u → v
w	3	u	u → w
x	5	u	u → x
y	9	w	u → w → y
z	10	w	u → w → z

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