edited by
20,570 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

18.2k
views
4 answers
61 votes
Kathleen asked Sep 17, 2014
18,158 views
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$ ... $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
13.5k
views
5 answers
24 votes
Kathleen asked Sep 16, 2014
13,512 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 onlyII, III and IV onlyI, III and IV only
6.6k
views
3 answers
25 votes
Kathleen asked Sep 15, 2014
6,649 views
Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph $G$ with $n*n$ adjacency matrix $A$ ... blanks.Fill in the blank: The running time of the Algorithm is $O$(___).
11.8k
views
4 answers
34 votes
Ishrat Jahan asked Oct 29, 2014
11,763 views
Consider a weighted, undirected graph with positive edge weights and let $uv$ be an edge in the graph. It is known that the shortest path from the source vertex $s$ to $u$ has weight ... $(u,v) = 12$Weight $(u,v) \geq 12$Weight $(u,v) > 12$