摘要: 城市道路网是在城市范围内由不同划分区位、运用功能、使用等级道路，以一定的空间密度和适当的安排形式组成的网络结构。随着当今社会节奏的加快，和汽车数量的陡增，交通问题日益凸显，人们纷纷使用智能交通系统，比如高德地图，百度地图等。本文中我们将采用四种不同的方法，专门在这样复杂的网络结构中，在确定出发点和最终到达点的条件下，对在城市道路中选择的路径进行了优化，使得路径和时间利用率达到最大化，也就是图论上的权值最大。

文中第一章主要介绍了本文所研究的城市道路网路径最优所涉及的理论背景以及研究意义。并且给出了路径最优问题的图论表示、连通图，出度，入度，权等关于图论的问题，还介绍了建立模型的方法以及求解模型的主要方法，包含Floyd算法，迪杰特斯拉算法，最小生成树法（避圈法、破圈法）以及动态规划法。第二章建立城市道路模型，用有向图表示路网，用节点表示交叉口，写出对于路径优化的方法步骤。第三章列举某个城市道路路径优化问题。首先建立某个城市部分交通网的图论模型，并运用动态规划法、迪杰特斯拉算法、Floyd算法、最小生成树法进行实例求解。第四章就本文所涉及的四种种方法：最小生成树以及动态规划法、迪杰特斯拉算法、Floyd算法的优缺点进行了对比分析。

关键词：城市道路网；最优路径；最小生成树法；动态规划 ；Floyd算法；迪杰特斯拉算法

目录

摘要

Abstract

1 绪论-4

1.1 理论背景及研究意义-4

1.1.1 理论背景-4

1.1.2 研究的意义-5

1.2 预备知识-6

1.2.1 图论的定义-6

1.2.2 图的分类-6

1.2.3 边、弧、入度、出度-7

1.2.4 连通图-7

1.2.5 权-7

1.3 研究现状及发展动态-7

1.3.1 Dijkstra(迪杰斯特拉)算法-7

1.3.2 Floyd(弗洛伊德)算法-8

1.3.3 最小生成树及其方法-9

1.3.4 动态规划法-9

2 建立模型以及解决方法步骤-10

2.1 节点-10

2.2 路段-11

2.3 方法及其步骤-11

3 实例分析-11

3.1 Dijkstra算法实例求解-11

3.2 动态规划法实例求解-14

3.3 最小生成树实例求解-16

3.4 Floyd算法实例求解-17

4 结论-21

参考文献-23

附录-24

致谢-28