2 You are running a delivery service and you want to optimize the cost of traveling...

 

Transcribed Image Text:

2 You are running a delivery service and you want to optimize the cost of traveling for your couriers. So, when trying to find shortest routes between delivery points your goal is to minimize not only the overall distance travelled but also the number of intermediate stops made by the couriers before reaching their final destination For example, in the graph shown, the shortest distance between nodes 1 and 3 is 5, so the courier should preferably go directly there from node 1 instead of going through node 2. Notice that both paths have the same length. Consider now the following definition 5 minStops [u] = minimum number of intermediate stops in a shortest path from s to u. Explain how to compute minstops [u], for every node u of a given graph. Show the modification of Dijkstra's algorithm, if necessary. 1 2 3 3 6 b) (10 points) Consider the following statements. Either prove them correct or give counterexamples (if they are not correct). 1. (3 pts) Dijkstra's algorithm does not work when the graph has edges with negative weights in general. But what if the only negative edges are the ones leaving the source s? Will the algorithm work? 2. 3. (3 pts) Suppose now you want to find the shortest path to some noder and you are told that the only negative edges are the ones entering t. Can the shortest path to be computed correctly by Dijkstra's algorithm? (2 pts) Suppose you have computed the shortest paths tree 7 from a sources to all other nodes and the weights of all edges increase by the same amount. Will 7 still be the shortest path in the new graph? (2 pts) Same as above but this time only the edges entering some node / are increased by the same amount. Will I still be the shortest path in the new graph? 4. 2 You are running a delivery service and you want to optimize the cost of traveling for your couriers. So, when trying to find shortest routes between delivery points your goal is to minimize not only the overall distance travelled but also the number of intermediate stops made by the couriers before reaching their final destination For example, in the graph shown, the shortest distance between nodes 1 and 3 is 5, so the courier should preferably go directly there from node 1 instead of going through node 2. Notice that both paths have the same length. Consider now the following definition 5 minStops [u] = minimum number of intermediate stops in a shortest path from s to u. Explain how to compute minstops [u], for every node u of a given graph. Show the modification of Dijkstra's algorithm, if necessary. 1 2 3 3 6 b) (10 points) Consider the following statements. Either prove them correct or give counterexamples (if they are not correct). 1. (3 pts) Dijkstra's algorithm does not work when the graph has edges with negative weights in general. But what if the only negative edges are the ones leaving the source s? Will the algorithm work? 2. 3. (3 pts) Suppose now you want to find the shortest path to some noder and you are told that the only negative edges are the ones entering t. Can the shortest path to be computed correctly by Dijkstra's algorithm? (2 pts) Suppose you have computed the shortest paths tree 7 from a sources to all other nodes and the weights of all edges increase by the same amount. Will 7 still be the shortest path in the new graph? (2 pts) Same as above but this time only the edges entering some node / are increased by the same amount. Will I still be the shortest path in the new graph? 4.

Answer rating: 100% (QA)

Part a Modifying Dijkstras Algorithm for minStopsu 1 Initialization Create arrays distu to store sho... View the full answer