in Algorithms retagged by
3,453 views
9 votes
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 _______

in Algorithms retagged by
by
3.5k views

1 comment

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

3 Answers

9 votes
9 votes
Best answer

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.$

selected by

3 Comments

nice question.
0
0
More like apti question
1
1
good question !
0
0
4 votes
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

1 comment

Correct.
2
2
0 votes
0 votes
Applying reverse of DJKstra will also work. i.e, Instead of selecting respective min adjacent, choose respective max adjacent
Answer:

Related questions