Graph Algorithm 19

21Let G = (V, E) be an undirected graph with a subgraph G₁ = (V₁, E₁). Weights are assigned to edges of G as follows:

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?

Option : B
Explanation :
Suppose G = (v, E) and G₁ = (v, E₁) such that E₁ ≤ E and v₁ ≤ v
Consider an example

Consider the w(e) = 1 of e ∉ E1 it means the cost of v₁ to v₄ is only 1 other edges having cost 0. It is noted that G₁ is connected (As shown in example).

Forgot your password?

I agree with the Terms.