3,453 views

In a directed acyclic graph with a source vertex $\textsf{s}$, the $\textit{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 $\textsf{s}$, the quality-score of $v$ is defined to be the maximum among the quality-scores of all the paths from $\textsf{s}$ to $v$. The quality-score of $\textsf{s}$ is assumed to be $1$.

The sum of the quality-scores of all vertices on the graph shown above is _______

### 1 comment

Applying reverse of DJKstra will also work. i.e, Instead of selecting respective min adjacent, choose respective max adjacent

Let $Q(v)$ denote the quality-score of vertex $v.$

1. $Q(s) = 1$
2. $Q(c) = 1*1\; (s \overset{1}{\rightarrow } c)$
3. $Q(f) = 1 * 1*9=9\; (s \overset{1}{\rightarrow} c \overset{9}{\rightarrow} f)$
4. $Q(a) = 1 * 9=9\; (s \overset{9}{\rightarrow}a)$
5. $Q(d)= 1 * 9* 1=9\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d)$
6. $Q(g)= 1 * 9* 1*9=81\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d\overset{9}{\rightarrow} g)$
7. $Q(b) = 1 * 9*1=9\; (s \overset{9}{\rightarrow}a\overset{1}{\rightarrow} b)$
8. $Q(e)= 1 * 9* 1*9=81\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d\overset{9}{\rightarrow} e)$
9. $Q(t)= 1 * 9* 1*9*9=729\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d\overset{9}{\rightarrow} e\overset{9}{\rightarrow} t)$

Therefore, the sum of the quality-scores of all vertices on the graph $= 2\times 1 + 4\times 9 + 2 \times 81 + 729 = 929.$

by

nice question.
More like apti question
good question !
S = 1 (Given)

C = 1 (S $\rightarrow$ C)

F = 1 * 9 (S  $\rightarrow$ C  $\rightarrow$ F)

A = 9 (S  $\rightarrow$ A)

D = 9*1 (S  $\rightarrow$ A  $\rightarrow$ D)

G = 9 * 1 * 9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ G)

B = 9 * 1 (S  $\rightarrow$ A  $\rightarrow$ B)

E = 9 * 1 * 9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ E)

T = 9*1*9*9 (S  $\rightarrow$ A  $\rightarrow$ D  $\rightarrow$ E $\rightarrow$ T)

Sum of quality-score of all vertices = 1+1+9+9+9+81+9+81+729 = 929

### 1 comment

Correct.
Applying reverse of DJKstra will also work. i.e, Instead of selecting respective min adjacent, choose respective max adjacent
by