Research And Implementation Of Optimal Paths Algorithm On Ticket Income Distribution System

Because of the high cost,large investments,long construction period and other factors of the track traffic,the construction process of the traffic road net in the whole city involves different investors,builders and managers.So we propose a Ticket Income Distribution System to distribute the ticket income reasonably,promptly and accurately to the relevant line.The establishment of Ticket Income Distribution System that needs to be resolved is the issue of the path between different sites of the lines,that is,solving K optimal paths between a pair of given points in undirected graph.After studying the problem of K optimal paths' basic theory,based on 2nd shortest path search algorithm and resort to the concept of "deviation" path,This paper proposes a new kind of kth shortest path search algorithm.Through K-1 times iteration of 2nd shortest path search algorithm,This algorithm can compute any two nodes assigned in the network.Due to the simply in the computation of 2nd shortest path search algorithm,this algorithm also has the traits of concise and fast.Using Fibonacci Heap to optimize the min priority queue of the Dijkstra Algorithm,that makes the performance of the Dijkstra Algorithm reach optimal.Aim at the decyclization that in the search and on the basis of the Delete Side Decyclization,we use the mind of 2nd algorithm,to make the new deviation path that is the second shortest path of the deviation path of the point that produce the decyclization.So that it can solve the bottleneck of the algorithm and make the efficiency of the algorithm have a distinct improvement.On the basis of this,we adjust the data structure referred,use adjacency multilist for storing Road network structure graph,whose MARK field can sign the path that the point in,so as to justify whether exist the decyclization.The fixed-length queue can store the paths that finally to be formed,to make the path unavailable can remove earlier,and further optimize the speed of the algorithm.The time complexity of the algorithm is O(VlgV+E+K~*m~*t).At last,validate the algorithm of the Shanghai track traffic road net,and confirm the algorithm that can solve some practical problem about plenty of nodes in connected graph Kth optimal path.