Please help on any part. I really need it. Thanks. For each of the following, de

Question

Please help on any part. I really need it. Thanks. For each of the following, decide whether the statement is true or false. Give a brief proof or convincing argument if the statement is true or a counterexample if it is false. (By using a "counterexample" to prove that a statement is false we mean that you should produce an instance of a shortest path problem that demonstrates that the statement cannot be true.) (16%) Dijkstra's method will always succeed in finding optimal distance labels if all arc lengths have the same sign. (16%) A shortest path problem is unbounded if contains a negative length directed cycle. (16%) Suppose we have a shortest path problem (P) in which the smallest arc length is cmin, where cmin

Explanation / Answer

1. Dijkstra's algorithm works only on non-negative edge weights, or non-negative arc lengths. If there are all negative arc lengths (same sign), we cannot apply Dijkstra's algorithm on that problem. Therefore, given statement is false. 2. It is true, since, if there is a negative weight cycle, then we can make a round once more among those edges to find a more less weight edge. In this case, cost becomes negative infinity. 3. Dijkstra's algorithm does not have negative weights of edges, or arc lengths. But since when we will add absolute value of c_min to form a problem Q, then every edge weight will be non-negative, so we can use dijstra's algortithm on Problem Q. Now, doing so, we can find optimal solution of Q. To find optimal solution for P, what we will do is that we will subtract absolute value of c_min on the edges of Q and the resulting graph will be the optimal solution for P. Therefore, given statement is true.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.