| The shortest - path problem in networks is a basic discrete optimzation problem and has a wide range of applications. All multi - stage decision proces with finite states can be changed into the shortest - path problem, which can be defined as follow 3 :Given a directed (or undirected) network N = ( V, A) with vertex set V and arc set A and a nonnegative weight Cj 0 associated with each arc e, (r A , the problem is to find a path from a distinguished source node s to a distinguished terminal node t, with the minimum total weight. The problems studied in this paper are further discussion about the shortest - path problem as follows:1. The neighborhood of the optimal solutions on the shortest - paths.2. The structure of the set of optimal solutions on the shortset - paths.3. The reduction model on the shortest - path with multiple sources and multiple terminals.1. The neighborhood of the optimal solutions on the shortest - paths in network.The concept and algorithms on the kth shortest - path problem have been introduced in the literatures(see[6, 9]). Based on them, the neighborhood of the optimal solutions about the shortest - paths in a network is studied in this paper. As a result, in scetion2.2.1, the idea of algorithms of finding equal potential subnetwork NO of N and algorithms 2.1 of finding all shortest - paths in network N are obtained sin section 2.2.2, the algorithm 2.2 of finding all paths which are not the shortest - paths and are in the neighborhood of the optimal solutions is also obtained.Theorem 1 All the shortest - paths with source s and terminal t in network N are included in the subnetwork N0 of N and N0 can be found polynomial-ly in O(m) time with m = | A |.Theorem 2 For any path with source s and terminal t in network N, If its total lengh is at most l * + e , then the shortest distince i from s to i of any intermediate node i must be at most / * + .Theorem 3 For any path P containing node i V \ V0 in network N, if its length l is at most l * + e , then32. The structure of the optimal solutions set on the shortest - pathsThe structure of the set of optimal solutions on the shortest - paths is studied in chapter 3. First, the sufficient conditions of having unique shortest - path in network N are discussed; Second, based on definition of 2 - transformation, the structural properties of 2 - transformation graph on the shortest - paths are studied particularly.theorem 4 A directed ( 5, t) path P of equal - potential subnetwork N0 is unique the shortest - path of N if and only if N0 has no double paths with equal length whose soure and terminal are on P.Theorem 5 2 - transformation graph of network N is a trivial graph if and only if the shortest - path is unique in N.Theorem 6 For any two directed paths PI and P2 with soure s and terminal t, if the subgraph constituted by Pt and P2 contains k double paths, then the 2 - transformation graph on the shortest-paths of the subgraph is a k - cube with 2 vertices.Theorem 7 If network N is a tree - like network and has at least two shortest - paths with source s and terminal t, then the 2 - transformation graph of the shortest - paths is a complete graph Ka where a is the number of the shortest - paths in network N.Theorem 8 If subnetwork N0 of any N is a tree - like network, then its 2 - transformtaion graph on the shortest-paths is complete graph Ka where a is the number of the shortest - paths in network N.Theorem 9 2 - transformation graph on the shortest - paths of network N is a connected graph.Theorem 10 If network N has at least 3 shortest - paths, then the girth of 2 - transformation graph of the shortest - paths equals 3 or 4.Theorem 11 If network N has at least 3 shortest - paths, then the 2 -transformation graph on the shortest - paths is Hamiltonian.Proposition If network N contains k shortest - paths, then the diameter of 2 - transformation graph on the shortest - paths in N is at most k - 1.3. The reduction model on the shortest - paths with multiple sources and multiple... |
PDF Full Text Request