edited by
19,897 views
86 votes
86 votes

Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows.

$$w(e) = \begin{cases} 0 \text{,   if } e \in E_1 \\1 \text{,   otherwise} \end{cases}$$

A single-source shortest path algorithm is executed on the weighted graph $(V,E,w)$ with an arbitrary vertex $v_1$ of $V_1$ as the source. Which of the following can always be inferred from the path costs computed?

  1. The number of edges in the shortest paths from $v_1$ to all vertices of $G$
  2. $G_1$ is connected
  3. $V_1$ forms a clique in $G$
  4. $G_1$ is a tree
edited by

5 Answers

Best answer
76 votes
76 votes

After applying the shortest path algorithm, check cost of vertex from source to every vertex in $G_1$. If $G_1$ is connected all these costs must be $0$ as edge weights of subgraph $G_1$ is $0$ and that should be the shortest path. If cost is not $0$, to at least one vertex in $G_1$ (not necessarily $G$), then $G_1$ is disconnected.

Answer is B.

edited by
21 votes
21 votes

yes. (b) is correct option!

6 votes
6 votes

Ans is (B)

When we compute shortest path from one of the vertex v1 in V1.Then we can infer as
G1 is connected if the cost from v1 to any other vertex in V1 is 1.
G1 is disconnected otherwise

5 votes
5 votes

Here we assume G is a connected Graph(Single source shortest path applied). Otherwise this question can not be solved based on the Given options.

Option A is incomplete.

Note:- Just like a graph could be disconnected, a subgraph could also be disconnected. Reference- https://www.youtube.com/watch?v=dPHkyRvLtIU

edited by
Answer:

Related questions

24 votes
24 votes
5 answers
2
Kathleen asked Sep 16, 2014
12,875 views
Consider the following graph: Among the following sequences:abeghfabfehgabfhgeafghbeWhich are the depth-first traversals of the above graph?I, II and IV onlyI and IV only...