In a directed acyclic graph with a source vertex s, the quality-score of a…
2021
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 v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.
The sum of the quality-scores of all vertices on the graph shown above is _______ .
Attempted by 72 students.
Show answer & explanation
Correct answer: 929
Key idea: compute the maximum product to each vertex using dynamic programming on the DAG. The quality-score of s is 1, and for any other vertex v, quality(v) = max over predecessors u of (quality(u) * weight(u→v)).
s = 1 (given).
a = 1 * 9 = 9 via s → a.
b = 9 * 1 = 9 via s → a → b.
c = 1 * 1 = 1 via s → c.
d = max(9 * 1 via s → a → d, 1 * 1 via s → c → d) = 9.
e = max(9 * 1 via s → a → b → e, 9 * 9 via s → a → d → e, 1 * 9 via s → c → d → e) = 9 * 9 = 81.
f = 1 * 9 = 9 via s → c → f.
g = max(9 * 1 via s → c → f → g, 9 * 1 * 9 via s → a → d → g) = 9 * 9 = 81.
t = max(81 * 1 via s → a → d → g → t, 81 * 9 via s → a → d → e → t, ... ) = 81 * 9 = 729.
Now sum the quality-scores: 1 (s) + 9 (a) + 9 (b) + 1 (c) + 9 (d) + 81 (e) + 9 (f) + 81 (g) + 729 (t) = 929.
A video solution is available for this question — log in and enroll to watch it.