Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights…
PYQ GATE 2003
Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights are assigned to edges of G as follows:
w(e) = 0, if e ∈ E₁
w(e) = 1, if e ∉ E₁
A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex v₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed?
- A.
The number of edges in the shortest paths from v₁ to all vertices of G
- B.
G₁ is connected
- C.
V₁ forms a clique in G
- D.
G₁ is a tree
Attempted by 187 students.
Sign up free to check your answer
Sign up freeLoading lesson…