K Shortest Paths Problem Algorithm And Its Application Research

The classic network shortest path(Shortest Path, SP) problem is aims to determine the shortest path between two nodes or from one given nodes to each other nodes in a static network, which has great application limitations. As an extension of SP problem, K shortest paths problem is expected to find K shortest paths, represent the solution set of decision problem in a oder of most-optimal, optimal, sub-optimal and so on,in a graph, which has a very wide range of applications such as in logistics, sequence alignment, network, and other text processing problems. Therefore, an efficient KSPalgorithm is undoubtedly very important and significant to solve practical problems. Recently, a wide range of application requirements to KSP algorithm has promote the study of KSP problem greatly and make it once again become a hot international topic in recent years.Compare with SP algorithm, the outstanding algorithm to solve KSP problem is scarce.This thesis studied existing research methods in KSP problem, achieved the following results:1. A heuristic search based method was proposed to solve single-pair KSP problem. This method used a searchstrategy that can be guided by heuristicand can perform on-the- fly feature on graph. Heuristic searchtry good choices first so that bad paths can be eliminated early and thus speed up the search. The on-the-fly strategy enables the partial generation and processing of the problem graph as needed by the search algorithm. This strategy is able to improve the performance and scalability of the algorithm. The correctness of the presented algorithm is analyzed mathematically, and the simulative results confirming the superior performance of the algorithm to others, especially when k is rather smal.2. Pulse coupled neural network and its application in KSP problem was studied. Proposed a Modified Continued Pulse Coupled Neural Network(MCPCNN) model to solve KSP problems.Theoretical analysis of MCPCNN and two algorithms for KSPs computation are presented. The computational complexity is only related to the length of the longest shortest path. Simulative results for route planning show that the performance of MCPCNN for KSPs computation outperforms many other current methods due to parallel pulse transmission characteristic of pulse coupled neural networks.3. A method to solve KSP problem was proposed, this method is based on the nature phenomenon of water flow, inspired by water flowing principle, and we imagine there are waters flowing from a source node to each other node along edges at a constant speed. When the water reaches a node, the node will generate new waters flowing along its outgoing edges. By stepping back the traces of the water, the ordered shortest paths can be obtained. We also address the correctness and effectiveness of the method. Simulations demonstrate the considerable performance of the proposed approach especially for single source KSP problems.