Official PYQ · 2004Q44Shortest Paths (Dijkstra, Bellman-Ford)MCQ1 mark

GATE CS 2004 Q44 — Shortest Paths (Dijkstra, Bellman-Ford)

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed graph with vertex $P$ as the source.

In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

View worked solution

Answer: B

Dijkstra's algorithm greedily selects the vertex with the minimum tentative distance that has not yet been finalized. Let $d(v)$ denote the shortest path estimate to vertex $v$ .

Starting with source $P$ ( $d(P) = 0$ and all other distances initialized to $\infty$ ):

Step	Vertex Finalized	$d(P)$	$d(Q)$	$d(R)$	$d(S)$	$d(T)$	$d(U)$
1	$P$	0	$1$	$5$	$\infty$	$\infty$	$\infty$
2	$Q$	-	1	$4$	$\infty$	$10$	$\infty$
3	$R$	-	-	4	$\infty$	$10$	$6$
4	$U$	-	-	-	$9$	$10$	6
5	$S$	-	-	-	9	$10$	-
6	$T$	-	-	-	-	10	-

Thus, the order in which the vertices are finalized is $P, Q, R, U, S, T$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Shortest Paths (Dijkstra, Bellman-Ford) questions

GATE CS 2004 Q44 — Shortest Paths (Dijkstra, Bellman-Ford)

Related questions