1. Describe algorithms for updating the shortest path distances from node s to every other node if we add a new node (n + 1) and some arcs incident to this node. Consider the following three cases:
(1) all arc lengths are nonnegative and node (n + 1) has only incoming arcs;
(2) all arc lengths are nonnegative and node (n + 1) has incoming as well as outgoing arcs; and
(3) arc lengths are arbitrary, but node (n + 1) has only incoming arcs. Specify the time required for the reoptimization.
2. Maximum mnltiplier path problem. The maximum multiplier path problem is an extension of the maximum reliability path problem that we discussed in Exercise 4.39, obtained by permitting the constants µij to be arbitrary positive numbers. Suppose that we are not allowed to use logarithms. State optimality conditions for the maximum multiplier path problem and show that if the network contains a positive mUltiplier directed cycle, no path can satisfy the optimality conditions. Specify an O(nm) algorithm for solving the maximum multiplier path problem for networks that contain no positive mUltiplier directed cycles.