Application of Improved Dijkstra Algorithm in Optimal Route Selection
Liao Xing-y · Modern Computer · 2013
In order to improve the efficiency of public travel,reduce the consumption of urban resources and optimize the urban environment,designs and implements the city bus lines inquiry system based on improved Dijkstra algorithm.Dijkstra algorithm is an excellent algorithm to solve the shortest path problems in the field of graph theory.Makes three major improvements on Dijkstra algorithm: optimizes the structure of the storage,classifies the nodes,sorts the weights and takes the improved Dijkstra algorithm as the core algorithm to query the best bus lines of urban public transport.Establishes mathematical models respectively with the evaluation criteria which composed by minimum of time,minimum cost and comprehensive optimal.Under these three demands,transforms the problem of searching the optimal route between two points into the problem of solving the shortest path between two points through the mathematical models.Takes the improved Dijkstra algorithm and the mathematical models for the simulation test.The simulation results demonstrate the effectiveness of the algorithms and data model.