摘 要

为解决道路拥堵，采用合适的手段搜寻两个地点之间的最短路径是最切实的办法。而这个办法的核心思想就是最短路径算法，在实际路网的单源最短路径算法中，应用最广泛的是Dijksatra算法^[1]。但是在实际问题中，Dijkstra算法往往存在很大冗余度，难以达到人们对于最短路径查询的实时性的要求。

本文的主要研究内容包括以下几个方面：

（1）对深度优先搜索以及广度优先搜索的研究，主要研究了深度优先 搜索尽可能深的搜索思想和广度优先搜索的逐层搜索思想的区别，并对比了两种搜索算法在数据存储结构，时间复杂度和优化方式等方面的不同。

（2）对Dijkstra算法和Floyd算法的研究，并在武汉市路网图上运用单源点最短路径算法-Dijkstra算来法进行实验，说明该算法是如何实现路径搜索的。

（3）针对Dijkstra效率低下的不足给出了数据存储结构、队列存储方式等方面的改进，并重点研究了改进后的A*算法，并分析改进前后两种算法的区别。通过这种改进的算法，可以提高实际运用的效率，尤其适用于大规模路网。

关键字：搜索算法；最短路径；Dijkstra算法；城市路网；A*算法

Abstract

Searching for the shortest path between two sites is a practical way to deal with road congestion, and the core idea of this approach is the shortest path algorithm, the most widely used in the actual path of the single source shortest path algorithm is Dijksatra algorithm. However, Dijkstra algorithm in solving practical problems, there is a lot of redundancy, it is difficult to meet people for the shortest path query real-time requirements.

The main contents of this paper include the following aspects:

(1) The study of depth-first search and breadth-first search mainly studies the difference between the deep-seated search as deep as possible and the breadth-first search, and compares the two search algorithms in the data storage structure, Time complexity and optimization of the different ways.

(2) Dijkstra algorithm and Floyd algorithm research, and in Wuhan road network map using Dijkstra algorithm to illustrate how the algorithm is to achieve the search.

(3) In view of the low efficiency of Dijkstra, the improvement of data storage structure is given, and the improved A * algorithm is studied emphatically, and the difference between the improved algorithm is analyzed. Through this improved algorithm, you can improve the efficiency of practical use, especially for large-scale road network.

Key Words：search algorithm；shortest path；Dijkstra algorithm；urban road network；A*

algorithm

目 录

第1章 绪论 1

1.1背景意义 1

1.2研究现状 1

1.3研究内容 2

1.4论文结构 2

第2章 搜索算法研究 4

2.1深度优先搜索 4

2.2广度优先搜索 5

2.3小结 6

第3章 最短路径算法研究 7

3.1概述 7

3.2Dijkstra算法 7

3.2.1Dijkstra算法概述 7

3.2.2Dijkstra算法思想 7

3.2.3Dijkstra算法描述 7

3.3Floyd算法 8

3.3.1Floyd算法概述 8

3.3.2Floyd算法思想 8

3.3.3Floyd算法描述 8

3.4本章小结 9

第4章 最短路径算法在路网中的应用 10

4.1路网数据获取 10

4.2路网特征介绍 10

4.3实验验证 10

第5章 最短路径算法的优化 13

5.1传统Dijkstra算法的不足 13

5.2Dijkstra算法优化思想 13

5.2.1存储结构优化 13

5.2.2数据队列优化 13

5.2.3启发式搜索 14

5.3Dijkstra算法和A*算法评价 15

第6章 总结与展望 17

6.1本文总结 17

6.2展望 17

参考文献 18

致谢 19

第1章 绪论

1.1背景意义

城市道路的建设随着经济的迅速发展而加快。与此同时，汽车数量迅猛增长，人们的生活节奏加快，出行变得更加频繁，这使得城市路网也变得越来越庞大和复杂，引发了车和路之间的巨大矛盾。调查发现，国内很多大城市的市区内行车速度甚至低于15km/h^[2]。人人渐渐发现，要依靠建设更多的道路，扩大道路网的规模，试图满足不断增长的交通需求，是不切实际的。于是，我们需要转变思路，考虑路径寻优的问题。

1. 最优的车辆行驶路径，能够使得资源和时间的利用最大化，因此，研究城市路网中两点间的最短路径问题有着十分重要的现实意义。对于个人来说，两个地点之间的最短路径可以大大缩短人们的出行时间，避免在城市道路中不必要的绕行，对于道路交通来说，可以提高交通的秩序性，减少交通拥堵和事故的发生，对于运输企业来说，选择一条最短的道路无疑是节约运输成本的最直接方式，对于医疗、火灾等应急事故来说，最短路径更是必须要考虑到的问题。最短路径算法是分配社会资源、规划方案和分析路线等改进问题的理论基础，在道路网图的研究、。城市交通线路的确定、。交通运输的最小耗费分析中均具有直接应用的价值。

1.2研究现状

最短路径的算法问题一直是各学科领域研究的热点问题，它不仅是图论的关键基础，还在计算机科学、交通工程学、运筹学、中有着重要运用，更是交通地理信息系统中的重要问题与研究热点，它是资源分配，线路优化等方面问题的基础。经典图论与计算机 数据结构和算法的不断发展相结合，使得各种新的最短路径算法层出不穷。最短路径算法可分为单源最短路径算法和全源最短路径算法等^[3]。

最短路径问题最早出现在五十多年前，迄今已有非常多的科学家对不同网络模型、不同条件的最短路径进行研究，在这些各式各样的最短路径算法中，Dijkstra算法是最为成熟和经典的最短路径算法代表。1959年，著名的荷兰科学家Edsger Wybe Dijkstra提出了现在广为人知的经典算法-Dijkstra算法，旨在解决一个确定点到其他各点的最短路径问题^[4]。随后，又有一些学者针对不同的前提对最短路径问题进行研究，除了经典的Dijkstra算法以外，常用的一些算法还包括：A*算法、。SPFA算法、。 Bellman-Ford算法和Floyd-Warshall算法等。它们在空间复杂度、 时间复杂度、 适用性以及应用范畴方面都有各自的特点。不过，。Dijkstra 算法仍然是最受学界认可并被广泛应用的，它的主要思想和特点是：以起始源点为中心 向外层层扩散，。直到扩展到终点为止。