Computer Sciences > GATE 2025 SET-2 > Graph Algorithms
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
A
Every MST remains an MST, and every SP remains an SP.
B
MSTs need not remain MSTs, and every SP remains an SP.
C
Every MST remains an MST, and SPs need not remain SPs.
D
MSTs need not remain MSTs, and SPs need not remain SPs.

Correct : c

Similar Questions

Consider the following algorithm someAlgo that takes an undirected graph G as input. The output of someAlgo (T) for the tree shown in the given figure is _____...
#1466 NAT
Consider the following algorithm someAlgo that takes an undirected graph G as input. The output of someAlgo (T) for the tree shown in the given figure is _____...
#1466 NAT
Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
#1386 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......
Question Options

Contributed by: