Computer Sciences > GATE 2026 SET-1 > Graph Algorithms
Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let s ∈ V be a vertex in G. For every u ∈ V and for every k ≥ 0, let dk(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then dk(u) = ∞.
Consider the statements:
S1: For every k ≥ 0 and u ∈ V, dk+1(u) ≤ dk(u).
S2: For every (u, v) ∈ E, if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every k ≥ 0, dk(u) ≤ dk(v).
Which one of the following options is correct?
Let s ∈ V be a vertex in G. For every u ∈ V and for every k ≥ 0, let dk(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then dk(u) = ∞.
Consider the statements:
S1: For every k ≥ 0 and u ∈ V, dk+1(u) ≤ dk(u).
S2: For every (u, v) ∈ E, if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every k ≥ 0, dk(u) ≤ dk(v).
Which one of the following options is correct?
Correct : a
Similar Questions
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...
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 foll...
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 _____...
Total Unique Visitors
Loading......