question 2

Suppose you are given a directed graph G with edge weights w(u, v) on each edge, and source s. Somebody has run Dijkstra's algorithm for you on this graph, and provides you with a length-n array dist, such that disti] contains the weight of the shortest path from s to i. Further, they also give you the shortest paths tree T, which you may assume is in an adjacency list format. As we know, running Dijkstra's algorithm on a graph takes time (m log(n)) (wen using a binary heap based priority queue). Now, suppose that you have dist and T available to you. The weight along one of the edges is decreased to w'(u, v), i.e. w'(u, v) 0. 1. Draw an example where the change in the edge weight doesn't change the distance of any of the nodes. Draw another example where it does. In your example you have to clearly indicate the weights, the updated weight and the distances before and after the change. 2. Design an algorithm that can update the distance of each node (if it changes at all) given the new edge weight. Your algorithm should run in O(n). 3. In class we said that in the general case Dijkstra's algorithm fails if there are negative edge weights in the graph. (We even saw an example) However, as it turns out, it works if we allow the outgoing edges adjacent to the source s to have negative weights. Prove that in this case Dijkstra's is indeed correct. Suppose you are given a directed graph G with edge weights w(u, v) on each edge, and source s. Somebody has run Dijkstra's algorithm for you on this graph, and provides you with a length-n array dist, such that disti] contains the weight of the shortest path from s to i. Further, they also give you the shortest paths tree T, which you may assume is in an adjacency list format. As we know, running Dijkstra's algorithm on a graph takes time (m log(n)) (wen using a binary heap based priority queue). Now, suppose that you have dist and T available to you. The weight along one of the edges is decreased to w'(u, v), i.e. w'(u, v) 0. 1. Draw an example where the change in the edge weight doesn't change the distance of any of the nodes. Draw another example where it does. In your example you have to clearly indicate the weights, the updated weight and the distances before and after the change. 2. Design an algorithm that can update the distance of each node (if it changes at all) given the new edge weight. Your algorithm should run in O(n). 3. In class we said that in the general case Dijkstra's algorithm fails if there are negative edge weights in the graph. (We even saw an example) However, as it turns out, it works if we allow the outgoing edges adjacent to the source s to have negative weights. Prove that in this case Dijkstra's is indeed correct