CSCI 570 Homework #5 SolutionProf. Ming-Deh HuangTAs: Iftikhar Burhanuddin, Chansook Lim11/04/03E. W. Dijkstra (1930-2002) Testing can show the presence of errors, butnot their absence.24.1-3We know that in the Bellman Ford Algorithm, values d[v] converge to lengthof the shortest path, from the source to node v. Moreover, these valuesconverge to their final values after m passes have been made w here m is thenumber of edges in the shortest path from s to v. Hence, if we modify thealgorithm, stopping after a pass in which none of th e d[v]’s were changed,we will have the desired algorithm.24.1-4Again we modify th e Bellman Ford Algorithm to obtain our new algorithm.Instead of exiting at the fir s t node where the triangle inequality is not satis-fied, we keep on going marking all the nodes for which the triangle inequalityis not satisfied. Once through we find all nodes reachable fr om the set ofthe marked nodes. This can be done by doing a BFS or DFS from themarked n odes. The correctness of the algorithm follows from the fact thateach negative weighted cycle has at least one marked node.24.1-6Let th e edge (v1, v2) be the one for which the triangle inequality is notsatisfied. It can be s hown that (v1, v2) is part of some negative weightedcycle {v1, v2, . . . , vk} where vk= v1. We fin d the shortest path f rom v2to v1using the Bellman Ford Algorithm again. Clearly, the weight of thispath would be less than or equal to the weight of the path {v2, v3, . . . , vk}.Appending the edge (v1, V2) to this path, we obtain a n egative weightedcycle.24.3-6We begin by noting that any simple path has weight at most W V becausethe weight of each edge is bounded by W and a s imple path has at mostV vertices. Next we observe that Dijkstra’s Algorithm functions like theBreadth First Search Algorithm over weighted edges, i.e. a node u whoseweight of the shortest path is less than that of a node v is always selected1before v. Now, using these facts we construct the O(W V + E) algorithm.We maintain an array A of size O(W V ). Each element in the array is apointer to a doubly-connected linked list. A node v is stored in the d[v]tharray position. We will need an other array B for indexing the position ofa node in the array A. Using this set up, we only need to traverse arrayA sequentially, getting rid of the EXT RACT MIN . O f course, we needto update the d values, however, using array B and the fact that th e nodesare stored in a doubly-connected list, updating would still take O(1) time.Hence, the overall complexity of the algorithm is O(W V + E).24.3-8Suppose the only edges that have negative weight are the ones which em-anate from the source vertex s. Now, the proof of correctness of Dijkstra’sAlgroithm requires non-negative weights of ed ges, however, the only placewhere it uses this facts is to take care of th e scenario that there might be apath through some other node that we haven’t seen uptil now. But, whenthe only negative weight edges are the ones directly emanating fr om thesource, then we don’t have this problem and the proof of correctness stillholds.25.2-6For each i, check if d(n)iiis less than 0. If there exists an i satisfying th eabove condition th en we have a negative-weight cycle.25.3-5We know that for a path p = {v0, . . . , vk}, ˆw(p) = w(p) + h(v0) − h(vk).Since for a cycle h(v0) = h(vk) and moreover w(c) = 0 for a 0-weight cyclec, hence, ˆw(c) = 0. This in conjunction with the fact that the values of ˆwis non-negative for all edges, leads to the fact that the value of ˆw for eachedge in a 0-edge cycle is 0.25.3-6The problem arises when we choose a vertex s, from w hich no negative-weight cycles are reachable. However, note that this is possible in directedgraphs w hich are not strongly connected. For example, consider the follow-ing graph which has four vertices, v1, . . . , v4with a negative-weight cyclev1, v2, v3. Also, there are three more edges (v1, v4), (v2, v4), (v3, v4). Now, ifs = v4, clearly Bellman Ford won’t be able to detect the negative-weight2cycle. Obviously, this problem is alleviated when the graph is strongly
View Full Document
Unlocking...