What are common examiner traps in Shortest Paths?

Updating vertex distance/parent pointers when equal to the existing distance under a 'strictly shorter' discovery specification. Confusing the general path-preserving property of w'(u,v) = w(u,v) + f(u) - f(v) (which holds for any function f) with the non-negativity requirement for Dijkstra's correctness (which requires specific distance potentials). Assuming DAG shortest paths require Dijkstra's priority queue overhead (m + n n) instead of linear-time topological sort (m + n). Overlooking multi-hop indirect paths when computing the shortest alternative path between two vertices in an adjacency matrix. Assuming that adding a constant positive scalar c to every edge preserves shortest paths (unlike potential reweighting, uniform scalar addition penalizes paths with more edges).

Shortest Paths

4 Qs · since 2012 · 8 marks · 0.3 marks/paperStandard yield

Take topic test

Shortest paths questions in GATE CS consistently assess both procedural graph execution (exact state transitions during relaxation under explicit tie-breaking conditions) and deep… Guide

Type

GATE CSE 2026 Set 2Q37MCQ2 marksEasyLet $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$ , which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from $s$ to all vertices that are reachable from $s$ …
GATE CSE 2020Q40MCQ2 marksMediumLet $G = (V, E)$ be a directed, weighted graph with weight function $w: E \rightarrow \mathbb{R}$ . For some function $f: V \rightarrow \mathbb{R}$ , for each edge $(u, v) \in E$ , define $w^{\prime}(u, v)$ as $w(u, v) + f(u) - f(v)$ . Which one of the options completes the following sentence so that it is TRUE?…
GATE CSE 2016 Set 1Q38NAT2 marksMediumConsider the weighted undirected graph with 4 vertices, where the weight of edge $\{i, j\}$ is given by the entry $W_{ij}$ in the matrix $W$ . $W = \begin{bmatrix} 0 & 2 & 8 & 5 \\ 2 & 0 & 5 & 8 \\ 8 & 5 & 0 & x \\ 5 & 8 & x & 0 \end{bmatrix}$ The largest possible integer value of $x$ , for which at least…
GATE CSE 2012Q40MCQ2 marksHardDiagramConsider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex $v$ is updated only when a strictly shorter path to $v$ is discovered.

Topic guide

What does GATE test in Shortest Paths?

Shortest paths questions in GATE CS consistently assess both procedural graph execution (exact state transitions during relaxation under explicit tie-breaking conditions) and deep structural properties of shortest path algorithms. Across the years, the topic spans algorithm tracing (Dijkstra), graph reweighting principles (Johnson's technique), parametric weight constraints, and optimal algorithmic bounds on specialized topologies (such as DAGs). Questions are invariably weighted at 2 marks, reflecting high conceptual and analytical rigor.

Core concepts

Dijkstra's algorithm execution, relaxation criteria, and tie-breaking mechanics
Single-Source Shortest Paths (SSSP) on Directed Acyclic Graphs (DAGs) using topological sort
Johnson's algorithm vertex potential reweighting and path invariance
Alternative shortest paths and metric constraints in weighted adjacency matrices
Time complexity trade-offs among shortest path algorithms (BFS, DAG relaxation, Dijkstra, Bellman-Ford, Floyd-Warshall)

Recurring question patterns

Exact Algorithmic Tracing with Strict Relaxation Rules
occasional · MCQ · 2 marks · 2012
Simulating Dijkstra's algorithm step-by-step on a directed weighted graph with specified tie-breaking or strictly-shorter update conditions to determine the exact path or parent pointers reported.
Parametric Edge Weight Threshold Analysis
occasional · NAT · 2 marks · 2016
Given a weighted graph or adjacency matrix containing an unknown parameter x on an edge, computing the threshold value of x such that the edge is included in at least one shortest path.
Path Invariant and Vertex Potential Reweighting
occasional · MCQ · 2 marks · 2020
Evaluating mathematical properties of edge weight modifications (e.g., adding node potentials $f(u) - f(v)$ ) and proving path optimality preservation via telescoping sums.
Complexity Bounds for Graph Subclasses
occasional · MCQ · 2 marks · 2026
Identifying the asymptotic time complexity of the fastest single-source shortest path (SSSP) algorithm on specialized graph classes, such as DAGs via topological ordering.

Formulas GATE uses

Telescoping Path Weight Modification (Johnson's Potential)

w^{\prime}(P) = \sum_{i=1}^k [w(v_{i-1}, v_i) + f(v_{i-1}) - f(v_i)] = w(P) + f(u) - f(v)

Used when analyzing the invariance of shortest paths under vertex potential reweighting functions.

DAG SSSP Running Time

T(n, m) = \Theta(n + m)

Used for finding single-source shortest paths in a Directed Acyclic Graph by relaxing edges along a topological ordering.

Shortest Path Edge Inclusion Bound

w(u, v) \le \text{dist}_{G \setminus \{(u, v)\}}(u, v)

Used to find the upper bound on an edge's weight such that the direct edge remains part of a shortest path between its endpoints.

Examiner traps in Shortest Paths

Updating vertex distance/parent pointers when equal to the existing distance under a 'strictly shorter' discovery specification.
Confusing the general path-preserving property of w'(u,v) = w(u,v) + f(u) - f(v) (which holds for any function f) with the non-negativity requirement for Dijkstra's correctness (which requires specific distance potentials).
Assuming DAG shortest paths require Dijkstra's priority queue overhead (m + n n) instead of linear-time topological sort (m + n).
Overlooking multi-hop indirect paths when computing the shortest alternative path between two vertices in an adjacency matrix.
Assuming that adding a constant positive scalar c to every edge preserves shortest paths (unlike potential reweighting, uniform scalar addition penalizes paths with more edges).

How questions are asked

Step-by-step tracing of Dijkstra's algorithm on a directed graph with tie-breaking rules
Parameter bounding for edge weights in an adjacency matrix to guarantee shortest path membership
Theoretical property verification of graph transformations and path potentials
Asymptotic worst-case complexity identification for restricted graph classes

Paper trends

Questions have diversified from manual Dijkstra tracing on visual graph figures to algebraic formulations, matrix-based path analysis, and theoretical properties of shortest-path-preserving transformations.
2026, 2020, 2016, 2012
Consistent high-value 2-mark allocation across all years, balancing procedural NAT questions with analytical and complexity-focused MCQs.
2026, 2020, 2016, 2012

Difficulty notes

Easy items test standard complexity bounds on specialized graph classes (e.g., DAG SSSP via topological sorting). Medium items test metric reasoning on adjacency matrices with symbolic variables or algebraic invariants like potential reweighting. Hard items require multi-step manual tracing on graphs with competing equidistant paths where strict relaxation and priority queue state transitions dictate the final parent pointers.