algorithms

Question

Let G1 (V, E) be a connected undirected graph and G2 (V1, E') be the subgraph of G1. Weights are assigned to the edges of G1.
W(e) = 0; if e belongs to  E'
         = 1 , otherwise.
Single source shortest path algorithms is applied on G1 and minimum path cost is computed between all pair of vertices and stored in a matrix.
What will be additional time complexity (strict upper bound) to determine if G2 is connected or not.

Answer 1

All the distances between source vertex and destination vertex using single source shortest path algorithm can be stored in a 1D matrix or array with each index i of array representing distance from source vertex to destination vertex i.

Since every edge in $G_{2}$ has weight 0, its shortest distance from source to all vertices will be 0. So we just have to check whether distance from source to all vertices is 0 or not in the 1D array by checking if value at index i is 0 or not. This can be done in linear time.

Hence, additional time complexity to determine if $G_{2}$ is connected or not is $O(n)$, where is the number of vertices in $G_{2}$. I hope this explanation makes sense.