True or False with topics on Dijkstra\'s Algo and Shortest Paths. 1. (15 points)

Question

True or False with topics on Dijkstra's Algo and Shortest Paths.

1. (15 points) True or False. Decide whether these statements are True or False. You must briefly justify all your answers to receive full credit (a) (5 points) If some edge weights are negative, the shortest paths from s can be obtained by adding a constant C to every edge weight, large enough to make all edge weights nonnegative, and running Dijkstra's algorithm. (b) (5 points) Let P be a shortest path from some vertex s to some other vertex t. If the weight of each edge in the graph is squared, P remains a shortest path from s to t c) (5 points) A longest simple path from s to t is defined to be a path from s tot that does not contain cycles, and has the largest possible weight Given a directed graph G with nonnegative edge weights and two nodes s and t, the following algorithm can be used to either find a longest simple path from s to t, or determine that a cycle is reachable from s . Negate all the edge weights » Run Bellman-Ford on the new graph. If Bellman-Ford finds a shortest path from s to t, return that as the longest simple path ? Otherwise, declare that a cycle is reachable from s Assume t is reachable from s

Explanation / Answer

1. False

Adding a constant edge weight C to increase every edge weight does not necessarily increase every path by the same amount of distance. Rather, the increase to the paths is often disproportional which depends on how many edges the path has. For example: suppose the lowest-cost edge has weight ?2 and there are two paths from a to b: a single edge of weight 3 and a path with two edges, each of weight 1. The two-edge path has the lowest weight. However, if you add 2 to every edge, the one-edge path has weight 5 but the two-edge path now has weight 6, so you get the wrong answer.

2. True

Square is an increasing function. So, if shortest path will remain short after squaring all edge weights.

3. True.

Th conventional Bellman-Ford algorithm finds the shortest path given negative edge weights. However, with negated weights, the largest edge weight will become least (most negative) and thus more likely to be included in the shortest path which will eventually give the longest simple path.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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