The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+35 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

asked in Algorithms by Veteran (69k points)
edited by | 2.6k views
Here our goal is to find shortest path so according to question the edge cost of G1 are 0 which leads to our goal shortest path so we try to contain max edge in G1 means we want to keep it connected.
I have a serious doubt here ... Can a single subgraph of a graph be disconnected ???

Consider this graph - 

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

3 Answers

+38 votes
Best answer

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.

Ans is B.

answered by Boss (8.6k points)
selected by
If cost of v1 to all the vertices in V1 is 0 connected, else disconnected.

According to question we are asked to apply single source shortest path algorithm on graph V and not on graph V1 using any vertex of subgraph V1 as source. So, Option (a) must be the correct answer because if we apply dijksta algorithm on graph V , we will always get number of edges in the shortest path from vertex V1 to all vertices of G.

gshivam63 See We are calculating the cost of for v1 of graph G1

which is a subgraph of G1 

and we know we can calculate cost for connected edges only

Here G1 is subgraph of G , which must be connected.

But G can be disconnected.

A) is not true because we are calculating shortest path for every subgraph  G1 ,not for G always . As G can be disconnected.

If u have any better example, u can give


The above example can help, where G and G1 are sample graphs in accordance with the specification in the question.

As we can clearly see the results of shortest path algorithm on G, we can say G1 is connected.


@srestha "which is a subgraph of G not  G1  i think ?

+7 votes

yes. (b) is correct option!

answered by Veteran (43.6k points)
What is the G itself is disconnected nothing is specified in the question about G if G is disconnected and is included in G1 then G1 won't be connected please help


 Which of the following can always be inferred from the path costs computed?

Answer =subgraph should be connected

which is actually wrong 



@Manu.What if g is not connected.?
If G is not connected then How can u apply single source shortest path algo on it on the basis of $G_{1}$ ?? according to the question ...
+5 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

answered by Boss (8.4k points)
I didn't understand the phrase "G1 is connected if the cost from v1 to any other vertex in V1 is 1"

Since, edges between vertices in v1 are having weight 0, how can the cost of any other vertex in v1 can be 1?

G1 is disconnected is the cost to any other vertex in G1 is having cost more than 0.

Please clarify.

@khush Tak: i think that G1 is connected if the cost from v1 to any other vertex in V1 is 0 " should be there . 


ok got it b is correct becz tree is a connected
connected property is  valid but these connection of graph is as per that so there will no formation of  cycle  which implies it will be a tree where every vertex is cover and acyclic graph is form

ans D;

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
38,801 users