The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+45 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 (52k points)
edited by | 4.7k 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.

Anyone please clear my doubt what is the meaning of option a i.e  the number of edges in the shortest paths from v1 to all vertices of G

4 Answers

+44 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.

Answer is B.

answered by Loyal (8.1k points)
edited 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 ?


Ayush Upadhyaya

I have one doubt can you please clear it



My doubt is  Graph G1 is a sub-graph of G which is connected right  in the above example that I give

But acc to " best answer " -- > If G1 is connected all these costs must be 0 as edge weights of sub-graph G1 is 0

but in the above case that i mentioned   It's not holds goods

Do  I analyze the question in a right way or did some mistakes   ??

please explain to me a little

@Magma, you have done your work correctly. Don't be confused, the cost of path to vertices A and B which are the only vertices in G1 came to be 0, means G1 is connected, otherwise for atleast one vertex in G1, cost would not have been 0.
+8 votes

yes. (b) is correct option!

answered by Boss (42.3k 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 ...
+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

answered by Loyal (6.8k 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;
+3 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.

answered by Active (1.8k points)

Nice answer 

@Nitesh Singh 2   what is the meaning of option A


Related questions

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
49,541 questions
54,084 answers
70,994 users