GATE CS 2003 Q67 — Shortest Paths (Dijkstra, Bellman-Ford)

To understand what can be inferred from the computed shortest path costs, let us analyze how the edge weights affect the path costs from the source vertex $v_1 \in V_1$:

• Edges belonging to the subgraph $G_1$ (i.e., $e \in E_1$) have a weight of $0$.
• All other edges in $G$ (i.e., $e \notin E_1$) have a weight of $1$.

Let $d(v_1, u)$ denote the shortest path cost from the source $v_1$ to any vertex $u \in V_1$. Since all edge weights are non-negative, $d(v_1, u) \ge 0$.

Analyzing Connectivity of $G_1$:

1. If $G_1$ is connected: For every vertex $u \in V_1$, there exists a path from $v_1$ to $u$ consisting entirely of edges in $E_1$. Since each of these edges has weight $0$, the total cost of this path is $0$. Thus, the shortest path cost $d(v_1, u) = 0$ for all $u \in V_1$.
2. If $G_1$ is disconnected: There exists at least one vertex $u \in V_1$ that is not in the same connected component as $v_1$ within $G_1$. Any path from $v_1$ to $u$ in $G$ must traverse at least one edge not in $E_1$ (which has weight $1$). Therefore, the shortest path cost $d(v_1, u) \ge 1$.

By checking if the computed shortest path cost from $v_1$ to all other vertices in $V_1$ is exactly $0$, we can uniquely determine (infer) whether $G_1$ is connected.

Eliminating Other Options:

• Option A: Since edges in $E_1$ have weight $0$, they do not contribute to the path cost. Thus, we cannot determine the actual number of edges in the shortest path.
• Option C: Path costs from a single source cannot determine if every pair of vertices in $V_1$ has an edge between them (clique property).
• Option D: Path costs of $0$ cannot detect the presence of cycles consisting of $0$-weight edges, so we cannot infer if $G_1$ is a tree (acyclic).