Skip to content
GATEiit

GATE CSE 2021 Set 2 Q65: Sum of maximum-product path scores in a weighted DAG

Question

In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex vv other than s, the quality-score of vv is defined to be the maximum among the quality-scores of all the paths from s to vv. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all the vertices in the graph shown above is ________.

DAG on a 3 by 3 grid. Edges with weights: s→c 1, s→a 9, c→f 9, c→d 1, a→d 1, a→b 1, f→g 1, d→g 9, d→e 9, b→e 1, g→t 1, e→t 9
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 929 (official GATE 2021 final answer key)

Concept used: Longest-path style dynamic programming in topological order, with product instead of sum.

First step: Process vertices in topological order: score(v) = max over incoming edges (u, v) of score(u) × w(u, v), starting with s = 1, c = 1, a = 9.

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 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 2 questions →