摘要现代意义上的最优路径已不再仅仅是指地理意义上的距离最短，它还可以是指时间最少、费用最省、线路容量最大等等。由于Dijkstra算法的本质求解单源点到所有顶点对的算法，且当其用于求解单对顶点间的最优路径时，计算必然存在冗余的问题，因此本文描述了基于规则限制的双向Dijkstra算法，该算法根据实际中的限制因素，动态的构建网络，减少了链接数量，有效提高了寻找最优路径的效率。双向Dijkstra搜索算法的效率比传统Dijkstra算法平均提高40％以上，而且图的顶点越多，效果越盟显。通过实际应用表明，该算法可以很好地满足路径选择的需要。67353

毕业论文关键词  最优路径  Dijkstra算法  双向搜索  

毕业设计说明书（论文）外文摘要

Title  City Transportation shortest path problem and the  algorithm research

Abstract

The optimal path no longer refers to the shortest distance in the modern sense, it can also refer to the least time,the least cost,the largest line capacity and so on.The essence of Dijkstra algorithm is to solve the distance of single source and all vertices , when it is used to find the optimal path,there must be redundancy problem.So this paper a two-way Dijkstra algorithm based on the limited rule.Relying on the actual constraints the algorithm constructs a network dynamically,reduces the number of links,and improves the efficiency of finding the optimal path.The efficiency of bi-directional Dijkstra Algorithm is generally more than 40% higher than that of the traditional Dijkstra Algorithm.The more vertexes there are on the map,the higher the efficiency will be.Through practical application ,it it show that the algorithm can be selected to meet to find the optimal path.

Keywords   Optimal Path  Dijkstra Algorithm  Bidirectional Search

 目 次

1  绪论 1

1.1  研究意义 1

1.2  国内外最短路径算法的发展及其概况 1

1.3 本文研究的问题及主题 4

2最短路径问题分析 6

2.1最短路径问题的分类和特点 6

2.2最短路径的搜索策略 7

2.2.1 深度优先搜索 7

2.2.2 广度优先搜索 7

2.2.3 启发式搜索 7

3  Dijkstra经典算法 9

3.1原理 9

3.1.1 Dijkstra算法的原理 9

3.1.2 Dijkstra算法的基本思想与步骤 9

3.1.3 Dijkstra算法的优缺点 11

3.2 Dijkstra算法与其他主流算法的比较 12

3.2.1 A*算法 12

3.2.2遗传算法 13

3.2.3  搜索速度比较 13

3.2.4搜索成功率比较 14

4  基于Dijkstra算法的改进算法的研究 16

4.1 双向Dijkstra算法的基本思路 16

4.2算法描述 17

4.3 算法优化