GATE 2021 CS (CS2) – Question 65

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

In the DAG shown with source s, a path’s quality is the product of its edge weights. A vertex’s quality is the maximum path quality from s; quality(s)=1. Find the sum of vertex qualities.

Diagram for GATE 2021 CS (CS2) question 65

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 929 to 929

Explanation

Process vertices in topological order, propagating products and taking maxima. The qualities are s=1, a=9, b=9, c=1, d=9, e=81, f=9, g=81, t=729. For example d→e has weight nine, giving e=81; e→t has weight nine, giving t=729. Their sum is 1+9+9+1+9+81+9+81+729=929.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2026 CS (CS1) Q41 – Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a…
GATE 2026 CS (CS1) Q49 – Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which…
GATE 2026 CS (CS1) Q50 – Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic…
GATE 2026 CS (CS2) Q37 – Let G be a weighted directed acyclic graph with m edges and n vertices. Given G and a…
GATE 2025 CS (CS1) Q18 – Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree…
GATE 2025 CS (CS1) Q43 – Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →