| The research about the shortest path is a hot issue in computer science. It has broad application area, communications and transport, rescue system, electronic navigation system and so on. The research about shortest path has both important theoretical significance and important utility value.Now, the classic algothrim about shortest path is Dijkstra algothrim and Folyd algothrim. These algothrim can just seek one shorest path of one pair of nodes and one shortest path of every pair of nodes. With the development of technology, this kind of algorithm can not solve many problems in practical application. For example, in the fields like rescue system center and transport dispatching center, what we need is not only paths between one pair of nodes or one shortest path but onmibearing information in order to dispatch flexibly. The article bases these, analyze and study the shortest path topic, the article proposes all shortest path of every pair of nodes and restricted all shortest path of every pair of nodes. These algorithm has great utility value in communications and transport, rescue system and so on.Firstly, this article introduces the present state and significance of the research about shorest path. Secondly, the theory of graph and the relevant knowledge of staple algorithm is introduced. Finally, analyze the shortest path algorithm and this altorithm proposed in this artile. The important part of this article is the forth chapter, three kinds of algorithm is proposed in this chapter.1.An basic algorithm of finding all shortest paths of every pair of nodes is proposed. This algorithm is based on the edge list in graph, relax the shortest path by adding every edge of the graph, update the length of shortest path of every pair of nodes, and keep the direct subsequence node, till all edges has been treated. and generate the all shortest path of every pair of nodes by travering the direct subsequence list. Its time complexity is max{O(n3*e), O(n*Shpath(G))} (n is codes sum in the graph, e is the edges number of the graph, Shpath(G) is the all paths number in the graph).2.An improved algorithm of finding all shortest paths of every pair of nodes is proposed. The algorithm strat from the node whose outdegree is zero, and update the shortest path length between every inverse adjacency node and the node and between every inverse adjacency node and the other nodes who is connect with the node, and set every inverse adjacency node's outdegree take away one, and remember the information of the subsequence node. Handle the nodes whose outdegree is zero in the same way. And then generate the all shortest paths with the the sequence list. Its time complexity is max{O(n3), O(n*allSH(G))} (n is codes sum in the graph, allSH(G) is the all paths number in the graph).3. An algorithm of finding all shortest paths of every pair of nodes which is vertices-constrained is put forward. The algorithm update the shortest path information of every pair of nodes in inverse topology order. And then generate the all vertices-constrained shortest paths by traversal. Its time complexity is max{O(e*n*Dsh(G)),0 (K*AllCfSh (G))} (n is codes sum in the graph, e is the edges number of the graph, Dsh(G) is the degree of the shortest path tree whose degree is the biggest in the shortest path forest, Dsh(G) is up to n, K is the contrained number of vertices in the graph, AllCfSh(G) is the all paths sum which is vertices-constrain in the graph). |
