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

Dark Mode

3,453 views

9 votes

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 _______

9 votes

Best answer

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

- $Q(s) = 1$
- $Q(c) = 1*1\; (s \overset{1}{\rightarrow } c)$
- $Q(f) = 1 * 1*9=9\; (s \overset{1}{\rightarrow} c \overset{9}{\rightarrow} f)$
- $Q(a) = 1 * 9=9\; (s \overset{9}{\rightarrow}a)$
- $Q(d)= 1 * 9* 1=9\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d)$
- $Q(g)= 1 * 9* 1*9=81\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d\overset{9}{\rightarrow} g)$
- $Q(b) = 1 * 9*1=9\; (s \overset{9}{\rightarrow}a\overset{1}{\rightarrow} b)$
- $Q(e)= 1 * 9* 1*9=81\; (s \overset{9}{\rightarrow} a \overset{1}{\rightarrow} d\overset{9}{\rightarrow} e)$
- $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.$

4 votes

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

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