Research On Shortest Path Problem Of Multi-stage Weighted Network With Quadratic Parameter

The shortest path problem for network is a topic in many fields of researches, such as computer science, geographic information and operations research. Now, the shortest path algorithm of static network has been considerably perfected. However, the research on the shortest path algorithm of dynamic network is comparatively weak. The static algorithm can only solve the shortest path problem of the network with the fixed topology and weight value. But it seldom works in problems of dynamic network we often actually encounter as the network topology and weight value changes based on time. The flourishing development of many fields like computer communication network, mobile communication network, distributed computing and intelligent traffic system, has forced people to deeply study this dynamic, variable, and more complicated shortest path problem of weighted network. Therefore, presenting the shortest path algorithm in dynamic network has been one of the hot researches in the problems of the shortest path.When the weight value in a network is a function with parameter instead of a constant, this network is a dynamic network. Computing the shortest path over this kind of network by traditional algorithm becomes very difficult, even impossible. When the weight value in a network is a function with quadratic parameter, this network is edge weights network with quadratic parameter.This paper studies the shortest path of multi-stage weighted network with quadratic parameter by the method from the general to the special. It studies the shortest path problem in multi-stage network with special quadratic parameter edge weights firstly, and in multi-stage network with common quadratic parameter edge weights secondly and thirdly in the mixed edge weights with linear and quadratic parameter. Adopting Dijkstra algorithm and implicit enumeration method, it obtains the following main outcomes on the basis of theoretical analysis:1. Present some implicit enumeration rules of the shortest path of multi-state weighted network with special quadratic parameter (3.1.3/3-1-1/lemma to 3-1-4/lemma); and on the basis of these rules show a shortest path algorithm (3.1.4/3-1/algorithm) and the critical point algorithm (3.1.5/3-2/algorithm);2. Present some implicit enumerative rules for the shortest path of multi-stage weighted network with general quadratic parameter (3.2.3/3-2-1/lemma to 3-2-4/lemma); and on the basis of these rules show a shortest path algorithm (3.2.4/3-3/algorithm) and the critical point algorithm (3.2.5/3-4/algorithm);3. Present some implicit enumerative rules for the shortest path of multi-stage weighted network with linear and general quadratic mixed parameter (4.3/4-3-1/lemma to 4-3-4/lemma), and on the basis of these rules show a shortest path algorithm (4.4/4-1/algorithm)and the critical point algorithm. (4.5/4-3/algorithm).This paper analyzes the computing complexity of the shortest path algorithm over the multi-stage network with linear and quadratic parameter mixed edge weights and shows that the shortest path algorithm proposed, though it is not polynomial, is quite effective in certain above mentioned network.