Success TrackerSuccess Tracker
Log inSign up

GATE CS 2021 Set 2 — Question 65

Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.
NAT+2 / -0MediumTopological SortGraph AlgorithmsAlgorithms

Algorithms → Graph Algorithms → Topological Sort

Last updated

Question

In a directed acyclic graph with a source vertex ss, 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 vv other than ss, the quality-score of vv is defined to be the maximum among the quality-scores of all the paths from ss to vv. The quality-score of ss is assumed to be 1.
A directed acyclic graph with source vertex s and other vertices a, b, c, d, e, f, g, t. Edges and weights are: s->c (1), s->a (9), c->f (9), c->d (1), a->d (1), a->b (1), f->g (1), d->g (9), d->e (9), b->e (1), g->t (1), e->t (9).
The sum of the quality-scores of all the vertices in the graph shown above is __________.
Your answer

Enter a number. Decimals, negative values and scientific notation are accepted.

The solution stays hidden until you check.

Continue learning with Success Tracker

A step still unclear? Work through it with support

Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.

AI-powered practice· Unlimited practice on eligible plans
PYQs with solutions
Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
Practice that adapts
Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
AI doubt support
Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.

Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.

Start with a free accountView plans and allowances

This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.

More questions on Graph Algorithms

2026 Set 1 Q17Consider the following recurrence relations: For all n>1n > 1,…2026 Set 2 Q24Consider the following functions, where nn is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array A=[10,7,8,19,41,35,25,31]A = [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort algorithm is…2026 Set 2 Q37Let GG be a weighted directed acyclic graph with mm edges and nn vertices. Given GG and a…