edited by
1,140 views
0 votes
0 votes
Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G as follows :

w(e) = 0 if e belongs to E1

1 otherwise

A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path costs computed?
(A) The number of edges in the shortest paths from ν1 to all vertices of G
(B) G1 is connected
(C) V1 forms a clique in G
(D) G1 is a tree

Plz tell the approach........
edited by

2 Answers

2 votes
2 votes
Answer is (B).

We can decide whether G1 is connected or not, because if it is connected then at least one path cost must be 1 because in shortest path computed from v1 to some vertex not in G1, we must include an edge not in G1, and weight of that edge is 1.

If path cost is 0 for all vertices, that means all the edges included were of weight 0 i.e. of G1 only, hence G1 is not connected.
1 votes
1 votes
I can certainly decide G1 is connected or not.initially I will set shortest distance from v1 to every vertex to infinity, then I will try to find the shortest path from v1 to all vertices.  Now after this algorithm terminates I will check if a vertex belongs to set V1 and contains infinity as the shortest  distance then G1 is disconnected graph else the graph is connected

Related questions

1 votes
1 votes
3 answers
2
3 votes
3 votes
2 answers
3
dd asked Dec 6, 2016
2,603 views
Let P be a shortest path from some vertex s to some other vertex t in a directed graph. If the weight of each edge in the graph is increased by one, P will still be a sho...
1 votes
1 votes
3 answers
4
Rakesh K asked Nov 27, 2016
3,097 views