Question

In a directed acyclic graph with source vertex \( s \), the quality-score of a directed path is the product of the weights of the edges on the path. 
For a vertex \( v \neq s \), the quality-score of \( v \) is the maximum among the quality-scores of all paths from \( s \) to \( v \). The quality-score of \( s \) is assumed to be 1. 
The sum of the quality-scores of all the vertices in the graph is \(\underline{\hspace{2cm}}\). 

Hint:

In DAG path problems, process vertices in topological order and propagate maximum path values forward.

Answer 1

Correct Answer: 929

We compute the quality-score of each vertex by taking the maximum product path from the source \( s \).

Step 1: Source vertex
\[ Q(s) = 1 \]

Step 2: Immediate neighbors of \( s \)
\[ Q(a) = 1 \times 9 = 9 \] \[ Q(c) = 1 \times 1 = 1 \]

Step 3: Next level vertices
\[ Q(b) = Q(a) \times 1 = 9 \] \[ Q(d) = \max(Q(a)\times 1,\; Q(c)\times 1) = \max(9,1) = 9 \] \[ Q(f) = Q(c) \times 9 = 9 \]

Step 4: Upper level vertices
\[ Q(e) = \max(Q(d)\times 9,\; Q(b)\times 1) = \max(81,9) = 81 \] \[ Q(g) = \max(Q(f)\times 1,\; Q(d)\times 9) = \max(9,81) = 81 \]

Step 5: Final vertex
\[ Q(t) = \max(Q(g)\times 1,\; Q(e)\times 9) = \max(81,729) = 729 \]

Step 6: Sum of quality-scores
\[ Q(s)+Q(a)+Q(b)+Q(c)+Q(d)+Q(e)+Q(f)+Q(g)+Q(t) \] \[ = 1 + 9 + 9 + 1 + 9 + 81 + 9 + 81 + 729 \] \[ = 929 \]

Final Answer: \[ \boxed{929} \]