Skip to content
GATEiit

GATE CSE 2026 Session 2 Q37: Fastest single-source shortest paths in a weighted DAG

Question

Let GG be a weighted directed acyclic graph with mm edges and nn vertices. Given GG and a source vertex ss in GG, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from ss to all vertices that are reachable from ss in GG?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2026 final answer key)

Concept used: In a DAG, relaxing edges in topological order gives shortest paths, even with negative weights.

First step: Topologically sort GG in O(m+n)O(m + n), then relax each vertex's outgoing edges once in that order.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 2 questions →