Computer Networks · TEE · papers

Q7A · Dijkstra with all intermediate steps

Final · 5 December 2025

TEE · Actual TEE paper · all questions · current syllabus 702AI0C023

Actual PYQ · Q7A. Consider a network topology consisting of nodes A, B, C, D, E, F, and G. The directed edges between these nodes and their corresponding positive weights are given in the table below. Using Dijkstra’s Algorithm: (i) Determine the shortest path from source A to destination G. (ii) Compute the shortest distance. (iii) Show all intermediate steps, including initialization and selection of the minimum-distance node for each iteration. (iv) Illustrate the original topology and final shortest path with edge distances. Directed edges: A→B=4, A→C=2, B→C=5, B→D=10, C→D=3, C→E=4, D→E=1, D→F=2, E→F=3, F→G=5. [10 marks]

Answer

Given

Edge	Cost
A→B	4
A→C	2
B→C	5
B→D	10
C→D	3
C→E	4
D→E	1
D→F	2
E→F	3
F→G	5

Source=A; target=G. Edges are directed; do not add reverse edges.

To find

The path A to G, its total cost and intermediate work.

Formula and why

d[v]\leftarrow\min(d[v],d[u]+w(u,v))

Use Dijkstra because all weights are nonnegative. Select the smallest unsettled total distance, not the cheapest isolated edge.

Dijkstra · given directed graph — Read the labels and direction before substituting numbers.

Step-by-step solution

Step 1. Initialize

d[A]=0; every other distance=∞. No predecessors are known.

Vertex	Distance from A	Predecessor	State
A	0	—	Tentative
B	∞	—	Tentative
C	∞	—	Tentative
D	∞	—	Tentative
E	∞	—	Tentative
F	∞	—	Tentative
G	∞	—	Tentative

Step 2. Settle A at distance 0

Unsettled candidates before selection: A=0, B=∞, C=∞, D=∞, E=∞, F=∞, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
A→B	∞	0+(4)=4	Improve to 4; predecessor=A
A→C	∞	0+(2)=2	Improve to 2; predecessor=A

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Tentative
C	2	A	Tentative
D	∞	—	Tentative
E	∞	—	Tentative
F	∞	—	Tentative
G	∞	—	Tentative

Step 3. Settle C at distance 2

Unsettled candidates before selection: B=4, C=2, D=∞, E=∞, F=∞, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
C→D	∞	2+(3)=5	Improve to 5; predecessor=C
C→E	∞	2+(4)=6	Improve to 6; predecessor=C

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Tentative
C	2	A	Settled
D	5	C	Tentative
E	6	C	Tentative
F	∞	—	Tentative
G	∞	—	Tentative

Step 4. Settle B at distance 4

Unsettled candidates before selection: B=4, D=5, E=6, F=∞, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
B→C	2	4+(5)=9	Already settled; retain
B→D	5	4+(10)=14	Retain 5

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Settled
C	2	A	Settled
D	5	C	Tentative
E	6	C	Tentative
F	∞	—	Tentative
G	∞	—	Tentative

Step 5. Settle D at distance 5

Unsettled candidates before selection: D=5, E=6, F=∞, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
D→E	6	5+(1)=6	Retain 6 (equal cost)
D→F	∞	5+(2)=7	Improve to 7; predecessor=D

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Settled
C	2	A	Settled
D	5	C	Settled
E	6	C	Tentative
F	7	D	Tentative
G	∞	—	Tentative

Step 6. Settle E at distance 6

Unsettled candidates before selection: E=6, F=7, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
E→F	7	6+(3)=9	Retain 7

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Settled
C	2	A	Settled
D	5	C	Settled
E	6	C	Settled
F	7	D	Tentative
G	∞	—	Tentative

Step 7. Settle F at distance 7

Unsettled candidates before selection: F=7, G=∞. Select the minimum; ties use alphabetical order.

Edge	Old distance	Candidate	Decision
F→G	∞	7+(5)=12	Improve to 12; predecessor=F

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Settled
C	2	A	Settled
D	5	C	Settled
E	6	C	Settled
F	7	D	Settled
G	12	F	Tentative

Step 8. Settle G at distance 12

Unsettled candidates before selection: G=12. Select the minimum; ties use alphabetical order.

No outgoing edges to relax.

Vertex	Distance from A	Predecessor	State
A	0	—	Settled
B	4	A	Settled
C	2	A	Settled
D	5	C	Settled
E	6	C	Settled
F	7	D	Settled
G	12	F	Settled

Step 9. Recover the path

Trace backwards: G ← F ← D ← C ← A. Reverse it: A → C → D → F → G.

Edge sum: 2 + 3 + 2 + 5 = 12.

Final answer: A → C → D → F → G; cost=12.

Dijkstra · final route and distances — Highlighted final route: A→C→D→F→G; total cost 12.

Source: Final · 5 December 2025, original question paper page 3. Original marks retained; solution independently authored.