改进型Dijkstra算法在最优路径选择中的应用研究

为了有效提高市民出行效率。减小城市资源消耗，优化城市环境，在改进型Dijkstra算法的基础上设计并实现城市公交线路查询系统。Dijkstra算法是图论中求解最短路径问题的一种优秀算法。在Dijkstra算法的基础上．进行对存储结构进行优化、对结点进行分类、对权值进行排序这三大改进．并将改进型Dijkstra算法作为最优公交线路查询算法的核心。以时间最小、费用最小、综合最优这三种需求作为评价标准分别建立数学模型，通过数学模型将搜索两点间的最优路线问题转化成求解两点间的最短路径问题．最后以南昌市的公交路网为例对算法和数学模型进行仿真测试。仿真结果验证算法和数据模型的有效性。

Application of Improved Dijkstra Algorithm in Optimal Route Selection

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 com- posed by minimum of time, minimum cost and comprehensive optimal. Under these three de- mands, transforms the problem of searching the optimal route between two points into the prob- lem 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.