GATE CS 2021 (Afternoon) — Question 65

AlgorithmsGraph Traversals (BFS, DFS) & Single-Source Shortest PathsNAT2 marksHard

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.
Question image
The sum of the quality-scores of all the vertices in the graph shown above is _________.
Practise the full 2021-AN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Graph Traversals (BFS, DFS) & Single-Source Shortest PathsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group