Analysis And Application Of K-Shortest Paths In The Network

Research on the network is becoming the important topic in today natural sciences, when modern society's already become the network society. The key point of the transportation network analysis is the way analysis, and the algorithm of the best route is the core of the way analysis. The shortest path algorithm is a classical problem of the best route algorithm, which has widespread application in many aspects. K-shortest path algorithm involves many domains, which is significant for traffic engineering, communication system, artificial intelligence and so on.Based on the systematic summarization and analysis of the classical shortest algorithm and dynamic layout theory, after careful research to the multi-paths of the traffic network, this paper is obtained K-shortest path algorithm, which is suitable for the analysis and simulation of network. This algorithm gives the increasing progressively the order of the K-shortest paths according to thelength. The algorithm complexity isO(m + nlgn + mlgk). On a given network, notonly the number of path-identifying stations and its position but also the number of total schemes of the path-identifying stations is calculated. To calculate the drifting traffic volume on the set of reasonable multi-ways of the networking highway, the heuristic search algorithm is applied to identify the value of the path stretching coefficient of the network, and then the scale of the set of the reasonable multi-ways is identified and the reasonable multi-ways between the two random stations on the given network is searched by the improved label method.