Discussion
Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.
Let \(s \in V\) be a vertex in G. For every \(u \in V\) and for every \(k \ge 0\), let \(d_{k}(u)\) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then \(d_{k}(u) = \infty\).
Consider the statements:
S1: For every \(k \ge 0\) and \(u \in V\), \(d_{k+1}(u) \le d_{k}(u)\).
S2: For every \((u, v) \in E\), if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every \(k \ge 0\), \(d_{k}(u) \le d_{k}(v)\).
Which one of the following options is correct?
Answer: A
Only S1 is true.
S1 holds because a path of length at most k is also a path of length at most k + 1. Allowing more edges can only add candidates, so the minimum weight cannot rise: \(d_{k+1}(u) \le d_{k}(u)\).
S2 fails because the shortest path through u may need more edges than a heavier path to v. Take vertices s, a, u, v with edges s-a, a-u and u-v of weight 1 and an edge s-v of weight 10. The shortest path to v is s-a-u-v (weight 3), so the edge (u, v) is part of it. For k = 1, however, u cannot be reached in one edge, so \(d_{1}(u) = \infty\), while \(d_{1}(v) = 10\) through the direct edge. Then \(d_{1}(u) \le d_{1}(v)\) is false.
So S2 is not always true, which rules out the options that accept it.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development