最短路径学年论文

. . .

. 摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。 关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab

目录 摘要··1 1引言··1 2最短路··2 2.1 最短路的定义 ·2 2.2最短路问题常见算法··2 3 Dijkstra算法··2 3.1 Dijkstra算法描述··2 3.2 Dijkstra算法举例··3 3.3算法的正确性和计算复杂性··5 3.3.1贪心选择性质··5 3.3.2最优子结构性质··6 3.3.3 计算复杂性··7 4 Floyd算法··7 4.1Floyd算法描述··8 4.2 Floyd算法步骤··11 4.3 Floyd算法举例··11 5 Dijkstra算法和Floyd算法在求最短路的异同··11 6 利用计算机程序模拟算法··11 7 附录··11 8 论文总结··13 9 参考文献··13 .

. 1 引言 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义

对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇

到的问题大都不含负权,所以我们在的0ijw的情况下选择Dijkstra算法。

定义1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。

定义2若图G=G(V,E)是赋权图且0We,eEG,假设[i,j] 的权记为ijW，,若i

与j之间没有边相连接，那么ij=W，。路径P的定义为路径中各边的长度之和，记W（P）。图G的结点u到结点v距离记为d(u,v)，则u、v间的最短路径可定义为minP0d(u,v)=,uvW（）

，不可达时。

2.2 最短路问题常见算法 在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。 Dijkstra算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为3On,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运

算效果要好于前者。 3 Dijkstra算法 3.1 Dijkstra算法描述 . . Dijkstra算法是解但愿最短路径问题的一个贪心算法。其基本思想是，设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是图G的某一顶点，把从源到u且中间只经过S中顶点的路称为源到u的特殊路径，并记录当前每个顶点所对应的特殊路径长度。Dijkstra算法每次从V—S中取出具有最短路径长度的顶点u，将u添加到S中，同时对短路径进行修改。一旦S包含了所有V中顶点，那么最后记录的最短路径就是源到所有其他顶点之间的最短路径长度。 算法要点如下： （1） 把V分为两个子集S和T。初始时，S={a}，T=V-S，其中a为源点； （2） 对T中每一个元素t计算D（t），根据D（t）值找出T中距a最短的一结点x，写出a到x的最短路径长度D（x）； （3） 更新S，置S为SU{x}，更新T，置T为T-{x}，判断条件：若T=，则终止，否则再重复（2）。 3.2 Dijkstra算法举例 问题的提出，给定一个带权有向图（既有向网）G和源点Vo，求Vo到G中其他每个顶点的最短路径。限定各边上的权值必须不小于0.如下图所示：

图1 公路网络赋权图 为了方便计算,先作出该网络的距离邻接矩阵,如下: 123456123456

05250159A21081058025910202520vvvvvvvvvvvv











设1234560,,,,,,jWvTvvsvvvvv,

1v 2v 3v 4v 5v 6v 1 2

5 5 5 5 8

10 2

2 .

. 第一次迭代 ①计算,2,3,4,5,6jTvj如下

22112min,min,055TvTvWvw

33113min,min,022TvTvWvw

44114min,min,0TvTvWvw

56,TvTv

②取

32minjjvsTvTv

,令332WvTv

③由于36kn,令2456,,,,3svvvvi转(1)

第二次迭代: ①算,2,4,5,6jTvj如下

22323min,min5,213TvTvWvw

44334min,min8,288TvTvWvw

55335min,min10,21010TvTvWvw

66336min,min,2TvTvWvw

②取

2min3jjvsTvTv

令223WvTv

③由于26kn,令456,,2svvvi转(1)

第三次迭代: ①算,4,5,6jTvj如下

44224min,min8,358TvTvWvw

55225min,min10,3910TvTvWvw

6Tv

②取

444min8,8jjvsTvTvWvTv

 . . ③由于46kn,令56,4svvi转(1)

第四次迭代: ①算,5,6jTvj如下

55445min,min10,2810TvTvWvw

66446min,min,8513TvTvWvw

②取

555min10,10jjvsTvTvWvTv



③由于56kn,令6sv转(1)

第五次迭代: ①算,6jTvj如下

66556min,min13,10212TvTvWvw

②由于6kn。因此已找到1v到6

v的最短距离为12。计算结束。

对应的迭代表格如下：

迭代 s u 2v 3v 4v 5v 6

v

1 {1} — 5 （2）    2 {1,3} 3

v （3） 2 10 12 

3 {1,3,2} 2

v 3 2 （8） 12 

4 {1,3,2,4} 4

v 3 2 8 （12） 15

5 {1,3,2,4} 5

v 3 2 8 12 （12）

找最短路线:逆向追踪得132456

vvvvvv

最短距离为12,即从城市1v到城市6

v的距离最短,即费用最省。

3.3算法的正确性和计算复杂性 3.3.1贪心选择性质

Dijkstra算法是贪心算法策略的一个典型例子。它所做的贪心选择是从V—S中选择具有最短特殊路径的顶点u，从而确定从源到u的最短路径长度dist[u]。这种贪心选择导致最