Most Dijkstra's algorithm questions test five ideas: its purpose, greedy rule, failure cases, data-structure complexity, and the unweighted special case. Two of those five are where hand-tracing usually breaks down: the order in which vertices get finalised, and which complexity bound belongs to which priority queue. Attempt each question before reading its explanation.
Nine of the twelve below come from previous-year GATE, UGC NET and state programmer papers, so the wording here is the wording examiners use. About 45 questions on this subtopic sit in the Algorithms learn module. For prerequisites, revise Graph Algorithms: BFS, DFS and Shortest Paths.
Warm-up: the problem Dijkstra actually solves
Dijkstra computes shortest paths from one source to every vertex when edge weights are non-negative. Prim and Kruskal build minimum spanning trees, Floyd-Warshall solves all-pairs shortest paths, and BFS or DFS does not generally handle weighted shortest paths.
Q1. Weighted shortest path, TPSC Programmer 2025
Which algorithm is used for finding the shortest path between nodes in a graph with weighted edges?
(a) Depth First Search (DFS)
(b) Breadth First Search (BFS)
(c) Dijkstra's Algorithm
(d) Kruskal's Algorithm
Answer: (c). DFS ignores weights. BFS works only when all edge weights are equal, as Q12 shows. Kruskal builds a minimum spanning tree, not shortest paths. Dijkstra handles non-negative weighted shortest paths.
Q2. Single-source shortest paths, UGC NET July 2018
Which of the following algorithms solves the single-source shortest paths problem?
(a) Prim's algorithm
(b) Floyd-Warshall algorithm
(c) Johnson's algorithm
(d) Dijkstra's algorithm
Answer: (d). Keep the jobs separate:
Algorithm | Problem solved |
|---|---|
Prim | Minimum spanning tree |
Floyd-Warshall | All-pairs shortest paths |
Johnson | All-pairs shortest paths, using reweighting and repeated Dijkstra runs |
Dijkstra | Single-source shortest paths |
The greedy engine and relaxation
Start with distance 0 for the source and infinity for every other vertex. Repeatedly settle the unvisited vertex with the smallest tentative distance, then relax each outgoing edge: if dist(u) + w(u,v) < dist(v), update dist(v). Choosing the current minimum is the greedy step; testing an improved route is relaxation.
Q3. Algorithmic paradigm, UGC NET January 2017
Dijkstra's algorithm is based on
(a) Divide and conquer paradigm
(b) Dynamic programming
(c) Greedy Approach
(d) Backtracking paradigm
Answer: (c). It repeatedly commits to the vertex with the smallest tentative distance. Reused shortest subpaths make dynamic programming tempting, but the selection rule and standard classification are greedy.
Q4. Meaning of relaxation, TPSC Programmer 2026
Which algorithm uses the concept of "relaxation" for finding shortest paths?
(a) Kruskal's algorithm
(b) Prim's algorithm
(c) Dijkstra's algorithm
(d) Topological sort
Answer: (c). Relaxation tests whether the current vertex gives a neighbour a smaller distance. Kruskal and Prim build spanning trees; topological sort only orders vertices.
Trace a full run: the GATE ordering question
With non-negative weights, an extracted vertex's distance is final. Its outgoing edges are relaxed when it is settled.
Q5. Can a cycle cause repeated relaxation?
If there is a cycle in a graph that is reachable from the source, then Dijkstra's shortest-path algorithm may relax an edge more than once in the graph.
(a) True
(b) False
(c) Sometimes yes, sometimes not
(d) None of the above
Answer: (b). Each vertex is settled once, and its outgoing edges are processed then. Each edge is therefore relaxed at most once, reachable cycle or not.
Q6. Finalisation order, GATE 2004
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?
Directed edges with weights: P->Q = 1, P->S = 6, P->T = 7, Q->R = 1, Q->S = 4, R->U = 1, S->T = 3, S->U = 2.
(a) P, Q, R, S, T, U
(b) P, Q, R, U, S, T
(c) P, Q, R, U, T, S
(d) P, Q, T, R, U, S
Answer: (b). Here is the full trace:
Start with P = 0. Its edges give Q = 1, S = 6 and T = 7.
Settle Q at 1. Then R = 1 + 1 = 2, while S improves to 1 + 4 = 5.
Settle R at 2. Then U = 2 + 1 = 3.
Settle U at 3. Nothing improves.
Settle S at 5. The alternatives T = 5 + 3 = 8 and U = 5 + 2 = 7 are worse than 7 and 3.
Settle T at 7.
The order is P, Q, R, U, S, T. Option (a) fails because U at 3 must be settled before S at 5. See the GATE 2004 Dijkstra ordering question with its solved answer.
Where Dijkstra breaks
Two traps recur. Negative edges break the settled-once guarantee, and shortest means minimum total weight, not the fewest vertices or edges.
Q7. Negative weight edges
Dijkstra's algorithm fails when ___________.
(a) Graphs are disconnected
(b) Graphs have negative weight edges
(c) Both (a) and (b)
(d) None of the above
Answer: (b). Take S->A = 4, S->B = 5 and B->A = -3. Dijkstra settles A at 4, but the true shortest route is S->B->A = 5 + (-3) = 2. A disconnected graph is fine; unreachable vertices remain at infinity.
Q8. Least weight is not fewest vertices, UGC NET December 2019
When using Dijkstra's algorithm to find the shortest path in a graph, which of the following statements is not true?
(a) It can find shortest path within the same graph data structure
(b) Every time a new node is visited, we choose the node with the smallest known distance/cost (weight) to visit first
(c) Shortest path always passes through least number of vertices
(d) The graph needs to have a non-negative weight on every edge
Answer: (c). Direct A->B of weight 10 uses two vertices. A->C->B has weight 3 + 3 = 6 and uses three, yet is shorter. Options (b) and (d) state the greedy rule and non-negative-weight requirement.
Complexity: match the data structure to the bound
Count V extract-mins and up to E decrease-keys: array O(V²), binary heap O(E log V), written equivalently as O((E + V) log V), and Fibonacci heap O(V log V + E).
Q9. Binary heap bound, GATE 2005
Let G(V, E) be an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
(a) O(|V|²)
(b) O(|E| + |V| log |V|)
(c) O(|V| log |V|)
(d) O((|E| + |V|) log |V|)
Answer: (d). The |V| extract-mins and up to |E| decrease-keys each cost O(log |V|), giving O((|E| + |V|) log |V|). Option (b) is the Fibonacci-heap bound because its decrease-key is amortised O(1). Review the GATE 2005 binary-heap complexity question with its solved answer.
Q10. Match implementation and complexity
Match the following time complexities of Dijkstra's algorithm with the corresponding priority queue implementations.
List A | List B |
|---|---|
P: Binary heap | X: O(V²) |
Q: Array | Y: O(E log V) |
R: Fibonacci heap | Z: O(V log V + E) |
(a) P-Y, Q-Z, R-X
(b) P-Z, Q-Y, R-X
(c) P-Y, Q-X, R-Z
(d) P-X, Q-Y, R-Z
Answer: (c). An array scans for the minimum V times, giving O(V²). A binary heap gives O(E log V); cheap Fibonacci-heap decrease-keys give O(V log V + E). Cheaper decrease-key removes the log from the E term.
Q11. Best choice for a dense graph, TPSC System Analyst 2026
The best implementation of Dijkstra's single-source shortest path algorithm on a dense graph G = (V, E) will use
(a) Adjacency matrix
(b) Adjacency list
(c) Binary min heap
(d) Fibonacci heap
Answer: (a). Dense means E is close to V². For V = 1000 and E about 10⁶, the matrix and array scan costs about V² = 10⁶ operations. A binary heap costs about E log₂ V = 10⁶ × 10 = 10⁷ operations. The extra log factor makes it slower here; heaps are most useful on sparse graphs.
The unweighted special case
When every edge has the same weight, tentative distance is simply the discovery layer. A FIFO queue replaces the priority queue, turning Dijkstra's logic into BFS.
Q12. Linear-time implementation, GATE 2006
To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:
(a) Queue
(b) Stack
(c) Heap
(d) B-Tree
Answer: (a). With equal weights, shortest means fewest edges. BFS explores in that order, and a queue gives O(V + E). A heap adds a log factor that buys nothing here; a stack gives DFS order, which is not shortest-path order at all. Open the GATE 2006 unweighted-graph question with its solved answer.
The short version and your next step
Dijkstra solves single-source shortest paths with non-negative weights.
Its greedy step settles the smallest tentative distance; relaxation updates a better route.
A settled vertex stays settled, and each outgoing edge is relaxed when its source is settled.
Negative edges break the guarantee. Shortest means least total weight, not fewest vertices.
The complexity ladder is O(V²), O(E log V), and O(V log V + E). On unweighted graphs, queue-based BFS is O(V + E).
The GATE questions above sit solved inside GATE Guidance by Sanchit Sir; the GATE CS preparation category gives the wider path. Re-attempt all twelve without notes, and for each one you miss, write down the rule you missed rather than the option letter.
