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 the vertices in the graph shown above is ______

Answer: 929 to 929

Explanation:

Given: 

Quality-Score of a directed path: Product of the weights of the edges on the path.

Quality-Score of a vertex: Maximum among the quality-scores of all the paths from s to v.

Quality-Score(s) = 1 

Quality-Score(a) = 9 ( only one path exist from s : s -> a)

Quality-Score(b) = 9× 1 = 9 ( only one exists from s: s -> a -> b)

Quality-Score(c) = 1 (only one path exists from s: s -> c)

Quality-Score(d) = Max(1 × 1 , 9 × 1) ( two paths from s: 1. s -> a -> d ; 2. s -> c -> d )

Quality-Score(d) = 9

Quality-Score(e) = Max(1× 1× 9 , 9 × 1× 9 , 9× 1× 1) ( 3 paths from s: 1. s -> c -> d -> e ; 2. s -> a -> d -> e ; 3. s -> a -> b -> e)

Quality-Score(e) = 81

Quality-Score(f) = Max(1× 9) ( only one path exists from s: s -> c -> f)

Quality-Score(f) = 9 

Quality-Score(g) = Max(1 × 9 × 1, 1 × 1 × 9, 9 × 1× 9) (3 paths from s: 1. s-> c -> f -> g; 2. s-> c-> d-> g ; 3. s->a->d->g) 

Quality-Score(g) = 81 

Quality-Score(t) = 729 ( total 6 paths exists;  Maximum product of weights will be of s->a->d->e->t : 9× 1× 9× 9)

Sum = Quality-Score(s) + Quality-Score(a) + Quality-Score(b) + Quality-Score(c) + Quality-Score(d) + Quality-Score(e) + Quality-Score(f) + Quality-Score(g) + Quality-Score(t)

Sum = 1 + 9 + 9 + 1 + 9 + 81 + 9 + 81 + 729 = 929