CSCI 570 Homework 5 Solution Prof Ming Deh Huang TAs Iftikhar Burhanuddin Chansook Lim 11 04 03 E W Dijkstra 1930 2002 Testing can show the presence of errors but not their absence 24 1 3 We know that in the Bellman Ford Algorithm values d v converge to length of the shortest path from the source to node v Moreover these values converge to their final values after m passes have been made where m is the number of edges in the shortest path from s to v Hence if we modify the algorithm stopping after a pass in which none of the d v s were changed we will have the desired algorithm 24 1 4 Again we modify the Bellman Ford Algorithm to obtain our new algorithm Instead of exiting at the first node where the triangle inequality is not satisfied we keep on going marking all the nodes for which the triangle inequality is not satisfied Once through we find all nodes reachable from the set of the marked nodes This can be done by doing a BFS or DFS from the marked nodes The correctness of the algorithm follows from the fact that each negative weighted cycle has at least one marked node 24 1 6 Let the edge v1 v2 be the one for which the triangle inequality is not satisfied It can be shown that v1 v2 is part of some negative weighted cycle v1 v2 vk where vk v1 We find the shortest path from v2 to v1 using the Bellman Ford Algorithm again Clearly the weight of this path 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 negative weighted cycle 24 3 6 We begin by noting that any simple path has weight at most W V because the weight of each edge is bounded by W and a simple path has at most V vertices Next we observe that Dijkstra s Algorithm functions like the Breadth First Search Algorithm over weighted edges i e a node u whose weight of the shortest path is less than that of a node v is always selected 1 before 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 a pointer to a doubly connected linked list A node v is stored in the d v th array position We will need another array B for indexing the position of a node in the array A Using this set up we only need to traverse array A sequentially getting rid of the EXT RACT M IN Of course we need to update the d values however using array B and the fact that the nodes are 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 8 Suppose the only edges that have negative weight are the ones which emanate from the source vertex s Now the proof of correctness of Dijkstra s Algroithm requires non negative weights of edges however the only place where it uses this facts is to take care of the scenario that there might be a path through some other node that we haven t seen uptil now But when the only negative weight edges are the ones directly emanating from the source then we don t have this problem and the proof of correctness still holds 25 2 6 n For each i check if dii is less than 0 If there exists an i satisfying the above condition then we have a negative weight cycle 25 3 5 We 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 cycle c hence w c 0 This in conjunction with the fact that the values of w is non negative for all edges leads to the fact that the value of w for each edge in a 0 edge cycle is 0 25 3 6 The problem arises when we choose a vertex s from which no negativeweight cycles are reachable However note that this is possible in directed graphs which are not strongly connected For example consider the following graph which has four vertices v1 v4 with a negative weight cycle v1 v2 v3 Also there are three more edges v1 v4 v2 v4 v3 v4 Now if s v4 clearly Bellman Ford won t be able to detect the negative weight 2 cycle Obviously this problem is alleviated when the graph is strongly connected 3
View Full Document
Unlocking...