1. (15 points) True or False. Decide whether these statements are True or False.
ID: 3709836 • Letter: 1
Question
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 to t 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
(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
it's false. Actually by adding constant to every edge may change the shortest path.
Consider a path sortest path having three edge of size one each and one more path having one edge of size 5.
1-----2------3------4 => 3
1-------------4=>5
in this case shortest path will be of three edge and total distance will be 3.
Now adding 4 in each edge will change the size of first path to 3 + 12= 15
and for second path size will be 5 + 4 = 9. hence path got change.
b) 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.
It's true.
multiplying all edge by a number will never change the shortest path can consider the same example.
Before:
1-----2------3------4 => 3
1-------------4=>5
now square of all weigth.
1-----2------3------4 => 3
1-------------4=>25
path remain same
(c) (5 points) A longest simple path from s to t is defined to be a path from s to t 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
it true.
By changing all edge to negative if return result that will be longest path
else it will declare that cycle is there.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.