Single-Source and All-Pairs Shortest Paths

Questions

1. GATE CS 2026 Set 1MCQ2 marksMedium (estimate)

   GATE CS 2026 Set 1, Q.41

   Let $G(V,E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the n...

   Single-Source and All-Pairs Shortest Paths

2. GATE CS 2026 Set 2MCQ2 marksEasy (estimate)

   GATE CS 2026 Set 2, Q.37

   Let $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 t...

   Single-Source and All-Pairs Shortest Paths

3. GATE CS 2025 Set 2MCQ2 marksEasy (estimate)

   GATE CS 2025 Set 2, Q.37

   Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following st...

   Minimum Spanning Trees · Single-Source and All-Pairs Shortest Paths

4. GATE CS 2016 Set 1NAT2 marksMedium (estimate)

   GATE CS 2016 Set 1, Q.48 (CS Q.38)

   Consider 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$…

   Single-Source and All-Pairs Shortest Paths

5. GATE CS 2013MCQ1 markEasy (estimate)

   GATE CS 2013, Q.19 (CS Q.19)

   What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of $n$ vertices?

   Single-Source and All-Pairs Shortest Paths

6. GATE CS 2012MCQ2 marksMedium (estimate)

   GATE CS 2012, Q.40 (CS Q.40)

   Consider 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 algorit...

   Single-Source and All-Pairs Shortest Paths · Greedy Algorithms

Other topics of Algorithms

• Asymptotic Analysis and Time/Space Complexity
• Searching and Sorting Algorithms
• Divide and Conquer
• Greedy Algorithms
• Dynamic Programming
• Graph Traversals, Topological Sort and Connectivity
• Minimum Spanning Trees