Research And Application Of Network Shortest Path Problem

The shortest path problem is the main problem of graph theory and the theory of network optimization, and it is mainly used to find the shortest path between any two points in the network. With the development of science and technology, the shortest path problem plays more and more important role in computer science, geographical information science, communication and military operations research and other fields. Therefore, it is significant to study the shortest path problem.Firstly, by analyzing the Bellman-Ford algorithm for repeated calculations, tedious looking for the shortest path problem, Ford improved algorithm is proposed in this paper. The improved algorithm by introducing the row array can reduce the time complexity of algorithm, at the same time with the former point label array enhanced the intuition of finding the shortest path. The improved algorithm is written into MATLAB program, and the simulation in large-scale random networks, the results show that the improved algorithm is more effective.Secondly, the paper studies Floyd algorithm, Floyd algorithm is improved by using iterative matrix and subscript tagging method. The improved algorithm improves the computational efficiency and simplifies the steps of finding the shortest path. The paper gives the time complexity, feasibility analysis and specific examples, Floyd improved algorithm and the original algorithm to calculate the shortest path in large networks, the theoretical analysis and simulation results illustrate the accuracy and efficiency of the improved algorithm.Thirdly, Topological sorting algorithm is complex that finding the shortest path. Modified algorithm is proposed with three value labels a node, it is easier that finding the shortest path by increasing the former point label. Modified algorithm only calculate node that connected with outgoing arcs of node and improves the efficiency.Finally, the paper introduces the application of the shortest path problem in communication and extends the application.