Problems And Application Research Of Network Shortest Path

The shortest path problem is an important branch of network optimization problem, It ismainly for solving the optimal path between any two vertices in the network, their research hasbeen quite a long history. The shortest path problem as the basis for selecting the optimal problem,in many application areas such as transportation and tourism, urban planning, engineering and so on,it has become an indispensable theoretical basis. However, for solving small-scale loop networkshortest path problem, most algorithms are based on the idea of Dijkstra algorithm or brute-forcemethod, not only the huge amount of computation, and complex operation.Firstly, this paper describes several classic algorithms for solving the shortest path problem,and in-depth analysis of the characteristics and the presence of defects of these algorithms, putforward a new simple methods, it is mainly through the elimination vertex and arc to simplify thestructure of the network diagram, and then get the shortest path and its length, and give the timecomplexity and feasibility analysis.Secondly, according to the ideas of the "arc suppression" algorithm, put forward the" matrix "algorithm，it is mainly through analysis of the first row elements of the weight matrix, andsimultaneously to eliminate the elements of the other rows and columns, finally obtained a sparsematrix containing the shortest path length, and get the shortest path, and give the time complexityand feasibility analysis.Thirdly, based on the relevant computer knowledge, the article describes the realizationprocess of the algorithm in the lingo software, and gives the specific network model, using theimproved algorithm above and lingo software to solve, All the results are consistent, validates thecorrectness of the algorithm.