06 Dec Shortest paths with some (i, j) < 0 when some link lengths on a network are negative the two shortest-path algorithms of section

 Shortest paths with some  (i, j) < 0 when some link lengths on a network are negative the two shortest-path algorithms of section 6.2 must be modified. algorithm 6.1 must be modified drastically, while only a minor modification is necessary in algorithm 6.2. in this problem we shall explore various aspects of the shortest-path problem with some (i, j) < 0.a.Let (f, e) = -2, instead of 5, in the graph of Figure 6.3. How would the shortest-path tree of Figure 6.5 change?b.Suppose that the following approach has been suggested for finding shortest paths on the graph of Figure 6.3 with (f, e) = -2: (i) Add 2 units to the length of all links of the graph so that all (i, j)  0; (ii) use Algorithm 6.1 to find any shortest paths required and then subtract 2 units from every link on each shortest path to find the true length of each shortest path. What is wrong with such an approach?c.Suppose now that (f, e) = -8 in Figure 6.3. What would now be the minimum distance between nodes a and j, d(a, j) ?

Hint: Be careful!

d.The phenomenon that you have observed in part (c) is referred to as a “negative cycle.” Whenever a negative cycle exists between two nodes of a graph, the shortest-path problem for this pair of nodes is meaningless. Note that this means that no undirected links on a graph should have negative (i,j)–since this immediately implies a negative cycle. Shortest-path algorithms must be able to “detect” the presence of negative cycles if they are to work with some  (i, j) < o. the key to such detecting is the following statement: in a graph with n nodes, no meaningful shortest path (i.e., one that does not indude a negative cycle) can consist of more than n – 1 links. argue for the validity of this statement.e.Algorithm 6.2 can be used as stated for cases where some (i, j) < o with only a minor modification to check for the existence of negative cycles upon termination. how would you use the final matrix d(n) at the conclusion of Algorithm 6.2 to check whether there are any negative cycles in a graph?

Hint: What should happen to one or more diagonal elements dn(i, i) of this matrix if there is a negative cycle in the graph ?

f.Repeat Example 2 of Section 6.2.2 for the case in which the length of the directed arc from node 5 to node 2 in Figure 6.6 is equal to -3.g.Can you suggest how shortest-path Algorithm 6.1 should be changed in order to be applicable to cases with some (i, j) < 0?

Hints: No labels can become permanent (i.e., nodes cannot become closed) until all labels are permanent; the algorithm requires at most N – 1 passes but may terminate earlier if no labels change during a pass.

For a more extensive discussion of algorithms of this type, see, for instance, Chapter 8, Section 2.2, of Christofides [CHRI 75]. 

https://web.mit.edu/urban_or_book/www/book/chapter6/problems6/6.1.html