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?
- The number of edges in the shortest paths from $v_1$ to all vertices of $G$
- $G_1$ is connected
- $V_1$ forms a clique in $G$
- $G_1$ is a tree