Algorithm Research On K-shortest Paths Of Network

The shortest path problem in network plays an important role in modern computer network and transportation network. It is a classical problem in the optimization. It has wide applications in production and our real life. In many cases, not only the shortest path is needed, but also the second shortest, the third shortest etc., which is k-shortest path. The applications of k-shortest path can be found in many fields such as communication, network, traffic engineering and artificial intelligence. The research on this problem has not only important theoretic significance but also great practical application value.This paper starts with the basic concepts of graph theory. Then, the detailed researches on the classic algorithms of the shortest path in graph theory and network have been made. The k-shortest path problem is studied from the views of graph theory, the optimization theory and the ant colony optimization, and some k-shortest path algorithms based on corresponding classic algorithms are obtained. The new algorithms are effective and practical. Moreover, their time complexities are given.First of all, basic concepts, related algorithms and the domestic and international development state in this research area are introduced. Detailed researches have been done on classic shortest path algorithms in graph theory and network, including Dijkstra algorithm and Floyd algorithm. Their advantages and disadvantages are summed up.Dynamic programming-based k-shortest path algorithm is given through the detailed analysis for dynamic programming in optimization theory by combining existing shortest path algorithm, which is easy to implement and effective. Deep analysis is made on minimum generation tree, Kruskal algorithm, Prim algorithm, depth priority algorithm and width priority algorithm, meanwhile their advantages and disadvantages have been summed. Based on construction algorithm of minimum generation tree, minimum generation tree-based k-shortest path algorithm is proposed, which has a high efficiency and practical application value.At last, the ant colony optimization is discussed. It is a new kind of imitating evaluation algorithm used to solve optimization problems, and shows strong ability to search optimal solutions in difficult situations and has lots of good properties. The ant colony optimization is tried to solve the shortest path problem, and the corresponding algorithm is given.