Research On Algorithm For All Constrained Shortest Paths

The shortest path algorithm is a hot subject in graph theory,geographical information system,and traffic advisory and so on.It has mainly application in path search,network optimization field.Dijkstra,Floyd algorithms are very classic ones among the shortest path algorithms.These algorithms only involve single-purpose optimization.They can only seek the shortest path length and one of the shortest paths.With the development of technology,single-purpose can describe and solve problems in true-life hard.So the shortest path algorithm restricted has strong utility value and extensive application area.This article based them starts discussing and researching the shortest path algorithm.This article proposes restricted shortest path algorithms.These algorithms have wide application and importance in physical distribution transit and determining traffic routes.This article first introduces current situation and meaning of researching the shortest path algorithm.Then it introduces graph theory and correlative knowledge of staple algorithms.Then it summarizes restricted shortest path algorithms and algorithms proposed in this article.This article importance lies in the third chapter.It proposes three kinds of related algorithm.1) Firstly,a shortest path algorithm which seeks all shortest paths from one code to another code in graphs is put forword.This algorithm treats its inverse adjacency code to tally down their outdegree from source.These codes which's outdegree are zero are handled in the same way,doing like this.The shortest path length and effective subsequence codes sequence from every code to destination are determined.This algorithm is easy to understand,and time complexity is low compared with others.Its time complexity is O(n~2×(sh1(G,i,j))(n is codes sum in graph,sh1(G,i,j) is number of the shortest paths in a graph).2) Secondly,a shortest path algorithm which is cost-constrained and vertices-constrained is put forword.It determines states which meet limiting conditions of every code's adjoining codes and stores thses states in these codes' state linked list.At last,there are all states which meet limiting conditions in linked list of destination.Among these states,one or more states which's path length is shortest is destination's state.At the same time,it can determine the second and third short paths. Its time complexity is O(n~2×N)(n is codes sum in a graph,N is the max number of nodes'states in graph).3) An improved shortest path algorithm which is cost-constrained and vertices-constrained is put forword.This algorithm uses nums of vertices-constrained as tree height,and cost-constrained condition as judgment condition to creat a shortest path tree which meet limiting conditions.Its time complexity is O(k×n×sh2(G,k,1)) (k is the constrained number of vertices in a graph,sh2(G,k,1) is number of the shortest paths whose cost and vertices are constrained in a graph).I carry out simulation experiments for kinds of algorithm proposed in this article in connection with every example graph,and analyze test result.Experiments indicate all algorithm correctness and high efficiency.Finally,I summarize and outlook all algorithms proposed in this article.