Shortest Path Algorithms MCQs For Gate Exam -

Shortest Path Algorithms

Dijkstra’s algorithm (using a binary heap) on a graph with (n) vertices and (m) edges runs in:
A) (O(n^2)) B) (O(m\log n)) C) (O(n\log n)) D) (O(m^2))
Answer: B.
Explanation: Each edge may cause a decrease-key; using a binary heap gives (O(m\log n)).
Dijkstra’s algorithm is incorrect if there are:
A) Negative edge weights B) Zero-weight edges C) Positive weights only D) Non-integer weights
Answer: A.
Explanation: Dijkstra relies on nonnegative edge weights to finalize distances.
Bellman–Ford detects negative-weight cycles reachable from the source in:
A) (O(nm)) time B) (O(n^2)) time C) (O(m\log n)) time D) (O(n)) time
Answer: A.
Explanation: Bellman–Ford relaxes all edges (n-1) times; extra pass detects cycles.
Floyd–Warshall computes all-pairs shortest paths in:
A) (O(n^3)) B) (O(n^2)) C) (O(mn)) D) (O(n\log n))
Answer: A.
Explanation: Three nested loops over (n) vertices.
Johnson’s algorithm reweights edges to remove negatives and then runs Dijkstra from each vertex. Its overall time is roughly:
A) (O(nm + n^2\log n)) B) (O(n^3)) C) (O(m\log n)) D) (O(nm\log n))
Answer: A.
Explanation: Bellman–Ford (O(nm)) for potentials + (n) Dijkstra runs.
Shortest paths in a DAG can be found in:
A) (O(n+m)) after topological sort B) (O(n^3)) C) (O(n\log n)) D) Impossible if negative edges
Answer: A.
Explanation: Relax edges in topological order — linear time.
If a graph has only nonnegative integer weights bounded by (W), Dial’s algorithm (bucket Dijkstra) runs in approximately:
A) (O(m + nW)) B) (O(m\log n)) C) (O(W\log n)) D) (O(n^2))
Answer: A.
Explanation: Buckets per distance value give (O(m + nW)).
For single-source shortest paths on an unweighted graph, best method is:
A) BFS B) Dijkstra C) Bellman–Ford D) Floyd–Warshall
Answer: A.
Explanation: BFS gives shortest paths in unit-weight graphs in (O(n+m)).
Relaxation of edge ((u,v)) updates (dist[v]) if:
A) (dist[u] + w(u,v) < dist[v]) B) (dist[u] > dist[v]) C) (w(u,v) < 0) only D) None
Answer: A.
Explanation: Standard relaxation condition.
After Dijkstra finalizes distance to a vertex, that distance can never be improved. True or False?
A) True B) False
Answer: A.
Explanation: With nonnegative weights, the first time a vertex is extracted yields shortest distance.
Bellman–Ford can compute shortest paths even when negative-weight edges exist but no reachable negative cycles. True or False?
A) True B) False
Answer: A.
Explanation: It handles negative edges; cycles detected by an extra pass.
If Bellman–Ford after (n-1) relaxations still improves some (dist[v]), then:
A) A negative-weight cycle is reachable B) Graph disconnected C) Dijkstra needed D) Floyd–Warshall fails
Answer: A.
Explanation: Improvement beyond (n-1) rounds implies negative cycle.
Dijkstra with Fibonacci heap runs in:
A) (O(m + n\log n)) B) (O(m\log n)) C) (O(n^2)) D) (O(m^2))
Answer: A.
Explanation: Fibonacci heaps give amortized (O(1)) decrease-key.
The shortest-path tree (SPT) from a source equals MST of same graph?
A) Not necessarily — different objectives B) Always equal C) Only in trees D) Only if graph complete
Answer: A.
Explanation: SPT minimizes distances from source; MST minimizes total edge weight.
If all edges have weight 1 except one edge of weight 1000, Dijkstra still finds shortest paths. True or False?
A) True B) False
Answer: A.
Explanation: Nonnegative weights OK; large weight just less preferable.
For a graph with (n=1000) and (m=999) (a tree), Dijkstra (binary heap) time ~:
A) (O(m\log n) \approx O(n\log n)) B) (O(n^2)) C) (O(1)) D) (O(n\log m))
Answer: A.
Explanation: Sparse graph; Dijkstra efficient.
In Johnson’s algorithm, edge reweight (w'(u,v) = w(u,v) + h(u) – h(v)): after reweighting, all (w’) are:
A) Nonnegative B) Negative C) Same as original D) Zero
Answer: A.
Explanation: Potentials (h) from Bellman–Ford ensure nonnegativity.
Floyd–Warshall can be used to detect negative cycles by checking:
A) Diagonal entries (dist[i][i] < 0) after algorithm B) Off-diagonals C) Degree counts D) Edge signs
Answer: A.
Explanation: Negative self-distance implies negative cycle.
The predecessor array in Dijkstra allows reconstructing shortest path in:
A) (O(length)) time per path B) (O(n)) per path always C) (O(1)) D) (O(m))
Answer: A.
Explanation: Backtrack predecessors along the path.
In a graph with negative-weight edges but no negative cycles, which algorithm is correct for single-source shortest paths?
A) Bellman–Ford B) Dijkstra C) Only BFS D) Floyd–Warshall (single-source not optimal choice)
Answer: A.
Explanation: Bellman–Ford handles negative edges from single source.
Dijkstra’s algorithm with adjacency matrix (dense graph) has complexity:
A) (O(n^2)) B) (O(m\log n)) C) (O(n\log n)) D) (O(n^3))
Answer: A.
Explanation: Simple array-based implementation is (O(n^2)).
A graph where negative-weight edges exist but no negative cycles reachable from source: Dijkstra or Bellman–Ford?
A) Bellman–Ford B) Dijkstra C) Both D) Floyd–Warshall only
Answer: A.
Explanation: Dijkstra can fail with negative edges.
Running Bellman–Ford on a graph with 1000 vertices and 10,000 edges costs about:
A) (O(nm)=10^7) relaxations B) (O(n^2)=10^6) C) (O(m\log n)) D) (O(n+m))
Answer: A.
Explanation: (n-1) rounds over all edges.
In an incremental scenario where one edge weight decreases, to update single-source shortest paths, one can:
A) Use decrease-key like updates (e.g., dynamic trees) or rerun algorithm depending on complexity; no simple constant-time update generally. B) Recompute from scratch always.
Answer: A.
Explanation: Decrease can be propagated with efficient priority updates or rerun.
The shortest path in terms of minimum number of edges (hop-count) in weighted graph can differ from shortest-weight path. True or False?
A) True B) False
Answer: A.
Explanation: Weight and hop count are distinct metrics.
Dijkstra’s greedy choice is to extract the unvisited vertex with:
A) Minimum tentative distance B) Maximum degree C) Maximum tentative distance D) Minimum degree
Answer: A.
Explanation: Extract-min picks vertex with smallest current distance.
Floyd–Warshall’s dynamic programming relation uses intermediate set ({1..k}). The recurrence:
A) (dist^{(k)}[i][j] = \min(dist^{(k-1)}[i][j], dist^{(k-1)}[i][k] + dist^{(k-1)}[k][j])) B) Max C) Sum D) Product
Answer: A.
Explanation: Standard DP for including vertex (k) as intermediate.
In Bellman–Ford, if you initialize (dist[s]=0) and others (\infty), after first pass some distances may become finite. True or False?
A) True B) False
Answer: A.
Explanation: First relaxation of edges updates reachable vertices within 1 edge.
For all-pairs shortest paths on sparse graphs (m << n^2), Johnson’s algorithm is usually preferable to Floyd–Warshall. True or False?
A) True B) False
Answer: A.
Explanation: Johnson uses Dijkstra (n) times with (O(nm + n^2\log n)) often better for sparse graphs.
Dijkstra cannot be made to work with negative edges even with potential reweighting unless potentials are known. True or False?
A) True B) False
Answer: A.
Explanation: Without valid potentials (from Bellman–Ford), nonnegativity not guaranteed.
Shortest path with exactly (k) edges can be solved in (O(n^3 \log k)) via repeated squaring of adjacency matrices with weights (min-plus algebra). True or False?
A) True B) False
Answer: A.
Explanation: Min-plus convolution and exponentiation approach.
In graph with nonnegative weights, the number of times a vertex’s distance decreases in Dijkstra is at most:
A) 1 (the final decrease when extracted) — actually it can be decreased multiple times before extraction, but decrease-key can happen up to degree times; but extracted once. Safer: each edge causes at most one decrease: so at most degree times. Let’s craft accurately.)
Rephrase: The number of times a vertex can be extracted (finalized) is:
A) 1 B) degree(v) C) log n D) n
Answer: A.
Explanation: Each vertex is extracted at most once.
If an edge weight is increased in a graph, single-source shortest paths can be updated by revisiting affected vertices. True or False?
A) True B) False
Answer: A.
Explanation: Increase may invalidate some paths; one can re-relax affected parts.
Bellman–Ford can detect negative cycles anywhere in graph or only those reachable from source?
A) Only reachable from source B) Anywhere globally C) Only in components with zero-weight edges D) Only directed cycles
Answer: A.
Explanation: BF relaxations start from source; unreachable cycles not detected.
For 2-terminal min-max path (minimize maximum edge weight along path), which structure solves all-pairs queries fast?
A) MST — the max-edge on path in MST is minimax value B) Shortest Path Tree C) Johnson’s reweight D) Bellman–Ford
Answer: A.
Explanation: MST minimizes bottleneck between any pair.
Dijkstra’s algorithm with adjacency list and binary heap on dense graph (m\approx n^2) behaves like:
A) (O(n^2\log n)) ~ worse than (O(n^2)) array Prim variant B) (O(m\log n)) better C) (O(n\log n)) D) (O(n))
Answer: A.
Explanation: Binary heap gives (O(m\log n)\approx O(n^2\log n)); array Prim is (O(n^2)).
SPFA (shortest path faster algorithm) is a queue-based Bellman–Ford improvement; worst-case can be:
A) Exponential or (O(nm)) depending on graph (pathological) — safe: can be (O(nm)) or worse in practice. Standard claim: worst-case exponential in some constructions. But for exam simple: worst-case (O(nm)).
Choose: A) (O(nm)) worst-case.
Answer: A.
Explanation: SPFA often fast but worst-case similar to Bellman–Ford.
For single-source shortest paths with nonnegative integer weights up to (W), radix-heap Dijkstra runs in:
A) (O(m + n\log W)) B) (O(m\log n)) C) (O(n^2)) D) (O(W^2))
Answer: A.
Explanation: Radix heap depends on range of distances.
In graphs with many negative-weight edges but no negative cycles, Johnson’s algorithm is still applicable. True or False?
A) True B) False
Answer: A.
Explanation: Bellman–Ford handles negatives to compute potentials.
Shortest simple path problem (no repeated vertices) with possibly negative weights is:
A) NP-hard in general (because of arbitrarily long negative cycles avoidance) B) Polynomial C) Solved by Dijkstra D) Solved by Bellman–Ford trivially
Answer: A.
Explanation: Constraining to simple paths with negative weights leads to NP-hardness.
To find k-shortest simple paths (distinct simple paths), Eppstein/Yen algorithms exist; simple repeated Dijkstra with path exclusion is:
A) Inefficient in general; better specialized algorithms exist B) Optimal C) NP-hard D) Not defined
Answer: A.
Explanation: Specialized algorithms produce k shortest paths efficiently.
In Floyd–Warshall, reconstructing actual path requires storing a next/predecessor matrix, else only distances known. True or False?
A) True B) False
Answer: A.
Explanation: Must record intermediate to reconstruct routes.
Bellman–Ford can be parallelized across edges in each relaxation round. True or False?
A) True B) False
Answer: A.
Explanation: Edge relaxations per round independent enough for parallelism (careful with writes).
For graphs with small diameter (D), multi-source BFS runs in about:
A) (O(n + m)) but number of levels ~(D) — overall linear. B) (O(D^2))
Answer: A.
Explanation: BFS cost linear in edges+vertices regardless of diameter.
In a graph where you need shortest paths from many sources but few destinations, best approach:
A) Run single-source algorithm from each source if sources few; otherwise use reverse graph if destinations few and run from each destination. B) Floyd–Warshall always better.
Answer: A.
Explanation: Choose algorithm based on source/destination counts.
Dijkstra’s algorithm on grid with 1000×1000 nodes (4 neighbors each) will take about:
A) (O(m\log n) \approx O(10^6\log 10^6)) B) (O(n)) C) (O(n^2)) D) (O(1))
Answer: A.
Explanation: Sparse graph with (m\approx 4n) edges.
If you need all-pairs shortest paths for n up to 400, Floyd–Warshall (O(n^3)) is often practical. True or False?
A) True B) False
Answer: A.
Explanation: 400^3 ≈ 64M iterations feasible in many setups.
In Dijkstra, if you use a pairing heap instead of Fibonacci, amortized practical performance is:
A) Comparable — theoretical differences smaller in practice. B) Much worse always.
Answer: A.
Explanation: Pairing heaps often competitive in practice.
For directed graphs, shortest path tree edges may form cycles if distances equal? (i.e., predecessor pointers forming cycles) — with correct algorithms, predecessor graph is acyclic away from zero-length cycles; answer: Predecessor tree is a directed tree (no cycles) if no negative zero-weight cycles. Generally predecessor pointers form arborescence.
Question: The predecessor subgraph returned by Bellman–Ford (if no negative cycles) is:
A) A directed forest / arborescence rooted at source B) Cyclic C) Arbitrary D) Undirected
Answer: A.
Explanation: Predecessors define a shortest-path tree/forest.
In a graph with nonnegative weights, if you relax edges in any order repeatedly until no change, you will converge to shortest paths (similar to Bellman–Ford) — true or false?
A) True (as long as no negative cycles) B) False
Answer: A.
Explanation: Repeated relaxations eventually propagate shortest distances.
The “potential” trick for reweighting edges (w'(u,v) = w(u,v) + \pi(u) – \pi(v)) preserves shortest-path order between any two vertices if potentials derived from node potentials. True or False?
A) True B) False
Answer: A.
Explanation: Reweighting keeps shortest path identity but makes weights nonnegative if potentials valid.
The shortest-path tree from source s has at most one outgoing edge per vertex (the parent pointer). True or False?
A) True B) False
Answer: A.
Explanation: Predecessor pointer unique per vertex (choose one if multiple equal-length paths).
For integer-weighted graphs with small max distance (C), 0-1 BFS (for weights 0/1) runs in (O(n+m)) using deque. True or False?
A) True B) False
Answer: A.
Explanation: Deque supports push-front for zero-weight edges.
The difference between Dijkstra and A* is:
A) Heuristic function guiding search to goal for A* while Dijkstra is uninformed. B) A* is slower always.
Answer: A.
Explanation: A* uses admissible heuristic to prune.
If an admissible heuristic h in A* is consistent (monotone), A*’s f-values are nondecreasing along paths and no re-expansions needed. True or False?
A) True B) False
Answer: A.
Explanation: Consistency ensures monotonicity and correctness.
For dynamic all-pairs shortest paths with edge updates, fully dynamic algorithms exist with polylog amortized time per update — true or false?
A) Partly true for restricted cases; general fully dynamic all-pairs is hard. Use approximate/dedicated methods. (Keep exam-level simple:)
Answer: A (Some algorithms exist with trade-offs).
Answer: A.
Explanation: Trade-offs and conditional results exist; exact fully dynamic APSP remains complex.
In directed acyclic graph, single-source shortest paths with possibly negative edges can be computed in:
A) (O(n+m)) via topological DP B) Bellman–Ford needed C) Dijkstra required D) Floyd–Warshall required
Answer: A.
Explanation: Topo order relaxations handle negatives as long as no cycles.
The breadth-first search tree can be used to compute shortest paths in unweighted graphs; weights of edges have no effect. True or False?
A) True B) False
Answer: A.
Explanation: BFS ignores weights and gives hop-count shortest paths.
The asymptotically fastest known exact algorithm for general integer-weighted single-source shortest paths uses:
A) Dijkstra variants and randomization; no known sub-(O(m + n\log n)) in general (sophisticated results exist). For exam: Dijkstra with Fibonacci heap (O(m + n\log n)) is best classic.
Answer: Dijkstra/Fibonacci heap standard.
Explanation: Advanced improvements exist under word-RAM models.
If edges have nonnegative weights but some vertices unreachable, Dijkstra returns (\infty) distances for unreachable vertices. True or False?
A) True B) False
Answer: A.
Explanation: They remain unvisited and distance stays infinite.
To compute shortest paths in Euclidean plane with obstacles, one can build visibility graph and run Dijkstra on it. True or False?
A) True B) False
Answer: A.
Explanation: Visibility graph nodes represent obstacle vertices; shortest path along visibility edges.
In Johnson’s algorithm, if Bellman–Ford detects negative cycle, then:
A) All-pairs shortest paths undefined (some pairs have no well-defined shortest) B) Reweighting proceeds anyway.
Answer: A.
Explanation: Reweighting infeasible; negative cycles preclude meaningful shortest paths.
Running Dijkstra on reverse edges and reversing parent pointers yields shortest paths to a single target in directed graph. True or False?
A) True (run Dijkstra on graph with all edges reversed from target) B) False
Answer: A.
Explanation: Reverse runs find distances to target.
In graph with edges of weight 1 and 2 only, a 0-1 BFS generalization using two queues can achieve (O(n+m)). True or False?
A) True B) False
Answer: A.
Explanation: Use deque trick with limited weights.
Theoretical lower bound for comparison-based single-source shortest paths (for real weights) is (\Omega(m + n\log n)) under certain models; Dijkstra matches it up to log factors. True or False?
A) True (model-dependent). B) False
Answer: A.
Explanation: Lower bounds depend on computation model; Dijkstra near-optimal.
For directed graphs with negative cycles, shortest path might be defined as (-\infty) for some pairs. True or False?
A) True B) False
Answer: A.
Explanation: You can loop negative cycles arbitrarily lowering path cost.
Using potentials to make edge weights nonnegative preserves shortest paths and allows Dijkstra to be used. True or False?
A) True B) False
Answer: A.
Explanation: Potentials maintain order of path lengths.
In practice, the main bottleneck of Dijkstra is decrease-key operations; pairing heap or binary heap implementations differ in performance. True or False?
A) True B) False
Answer: A.
Explanation: Implementation choice affects performance.
For large graphs and many source queries, multi-source Dijkstra (multi-source BFS generalization) can be used by initializing multiple sources in heap. True or False?
A) True B) False
Answer: A.
Explanation: Push all sources with zero distance and propagate.
For APSP on graphs with small integer weights, repeated convolution or distance product via min-plus algebra and fast convolution can help. True or False?
A) True (specialized techniques exist) B) False
Answer: A.
Explanation: Algebraic methods accelerate for bounded weights.
Katz centrality / commute times relate to distances in graph Laplacian, but computing them requires solving linear systems, not only shortest paths. True or False?
A) True B) False
Answer: A.
Explanation: Spectral quantities differ from shortest-path metrics.
For grid navigation with obstacles, A* with admissible heuristic (Euclidean distance) often outperforms Dijkstra. True or False?
A) True B) False
Answer: A.
Explanation: Heuristic guides search reducing explored nodes.
If you have to find shortest paths under time-dependent edge weights (travel times vary with departure time), standard static Dijkstra is not correct. True or False?
A) True B) False
Answer: A.
Explanation: Time-dependent shortest paths require specialized algorithms.
In some road networks, contraction hierarchies preprocess and enable very fast shortest-path queries. True or False?
A) True B) False
Answer: A.
Explanation: Preprocessing shortcuts accelerates queries.
Edge-disjoint shortest paths problem (find multiple shortest paths not sharing edges) is:
A) NP-hard in general for k>1 under some formulations B) Trivial C) Solved by single-source Dijkstra repeatedly with edge removals D) Equivalent to MST
Answer: A.
Explanation: Constraint makes problem combinatorially hard.
The potential-based reweighting used in Johnson ensures no negative cycles if initial BF succeeded. True or False?
A) True B) False
Answer: A.
Explanation: BF finds feasible potentials if no negative cycles reachable.
For graph with edge weights drawn from small set (e.g., {1,2,…,10}), bucket-based Dijkstra runs in near-linear time. True or False?
A) True B) False
Answer: A.
Explanation: Buckets give (O(m + nW)) with small (W).
Dijkstra produces shortest path distances but not necessarily unique paths. To get lexicographically smallest path among equal-length paths, modify tie-breaking in predecessor selection. True or False?
A) True B) False
Answer: A.
Explanation: Tie-breaker choice controls which path recorded.
Single-source shortest paths in planar graphs can be faster than general graphs using planar separators. True or False?
A) True B) False
Answer: A.
Explanation: Planarity allows algorithmic speedups.
For graphs with very large (n,m) (big data), approximate shortest paths (e.g., landmarks, sketching) are often used in place of exact algorithms. True or False?
A) True B) False
Answer: A.
Explanation: Approximation trades accuracy for speed/space.
Min-plus matrix multiplication (distance product) is semiring-based and underlies Floyd–Warshall. True or False?
A) True B) False
Answer: A.
Explanation: Replace +/* with min/+ yields distance product.
Finding shortest cycle through a given vertex is reducible to single-source shortest paths by removing the vertex and combining paths. True or False?
A) True (compute shortest path between neighbors) B) False
Answer: A.
Explanation: Check shortest u→v path for neighbors u,v of vertex.
For graphs with negative cycles but constraints disallow repeating cycles, problem of shortest simple path is NP-hard. True or False?
A) True B) False
Answer: A.
Explanation: Simple path restriction makes problem hard.
Dijkstra can be adapted to find longest paths if all weights are negative and no positive cycles. True or False?
A) False — longest path problem is NP-hard even in DAG? Actually longest in DAG polynomial via topo DP. But adapting Dijkstra is not possible generally. So answer: False.
Answer: A (False).
Explanation: Longest path in general graphs is hard; in DAGs doable via DP.
Edge weights scaling by positive constant preserves shortest paths. True or False?
A) True B) False
Answer: A.
Explanation: Multiplying all weights by c>0 preserves ordering of path costs.
The k-th shortest path (allowing repeats) can be found using variants of Dijkstra with path counting (Eppstein). True or False?
A) True B) False
Answer: A.
Explanation: Algorithms exist for k-shortest walks/paths.
For sparse graphs with (m = O(n)), Dijkstra (binary heap) runs in about (O(n\log n)). True or False?
A) True B) False
Answer: A.
Explanation: If m=Θ(n), m log n = n log n.
Shortest path tree may differ depending on tie-breaking of equal alternative predecessors, but all distances preserved. True or False?
A) True B) False
Answer: A.
Explanation: Multiple SPTs possible with equal path lengths.
To detect negative cycles reachable from any vertex (global), run Bellman–Ford from each vertex separately. True or False?
A) True (but expensive); alternatives include other algorithms) B) False
Answer: A.
Explanation: Running BF from each source catches cycles reachable from that source; global detection can be done by adding super-source connecting to all vertices then BF once.
The problem of constrained shortest path (limit on cost and minimize time) is NP-hard (multi-criteria shortest path). True or False?
A) True B) False
Answer: A.
Explanation: Multi-criteria optimization becomes NP-hard in general.
Floyd–Warshall can be modified to output next-hop matrix to reconstruct shortest path in (O(length)) time. True or False?
A) True B) False
Answer: A.
Explanation: Store intermediate; reconstruct by recursion.
For integer weights, Thorup’s algorithm finds single-source shortest paths in linear time (O(m)) on undirected graphs. True or False?
A) True (under RAM model and integer weight assumptions) B) False
Answer: A.
Explanation: Thorup’s algorithm is linear-time in undirected integer-weighted case.
The shortest path in time-dependent networks (FIFO property holds) can be computed by time-expanded Dijkstra. True or False?
A) True B) False
Answer: A.
Explanation: Time-expanded graphs model time windows; may be large.
Reweighting trick (w'(u,v) = w(u,v) + h(u) – h(v)) preserves shortest paths lengths up to additive constants. True or False?
A) True B) False
Answer: A.
Explanation: Shortest path length differences preserved.
In a directed acyclic graph, the longest path can be found by negating weights and running shortest path DP via topo order. True or False?
A) True B) False
Answer: A.
Explanation: DAG allows longest path via topo DP even with positive weights (negation).
For road networks, algorithms exploit small highway dimension to speed up queries. True or False?
A) True B) False
Answer: A.
Explanation: Low highway dimension yields hierarchical shortcuts.
Using bidirectional Dijkstra (search from source and target) often speeds up point-to-point queries in practice. True or False?
A) True B) False
Answer: A.
Explanation: Meet-in-the-middle reduces explored area.
If we want shortest paths modulo a large prime (min-plus with modulo), operations do not form a well-defined semiring preserving shortest-path semantics. True or False?
A) True — modulo breaks comparisons/min semantics B) False
Answer: A.
Explanation: Min-plus algebra incompatible with modulo arithmetic.
The concept of “shortest path with resource constraints” (e.g., fuel capacity) typically needs label-setting or label-correcting algorithms and is NP-hard in general. True or False?
A) True (complex) B) False
Answer: A.
Explanation: Additional constraints often make problem combinatorial.
Final conceptual: The correctness proof of Dijkstra uses which invariant?
A) When a vertex is extracted from the priority queue, its distance is the shortest possible (invariant). B) When a vertex inserted, it’s final.
Answer: A.
Explanation: The extract-min invariant under nonnegative weights proves correctness.