图论最短路径分析及应用.doc

最短路问题及其应用
1 引言
图论是应用数学的一个分支，它的概念和结果来源非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博弈问题、棋盘上马的行走路线问题等． 这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题．
1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在实践中，图论已成为解决自然科学、工程技术、社会科学、军事等领域中许多问题的有力工具之一。
最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。
最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。
2 最短路
2.1 最短路的定义
对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法。
定义①1若图G=G(V,E)中各边e都赋有一个实数W(e),称为边e的权,则称这种图为赋权图,记为G=G(V,E,W)。
定义②2若图G=G(V,E)是赋权图且,,若u是到的路的权,则称为的长,长最小的到的路称为最短路。
若要找出从到的通路,使全长最短,即。
2.2 最短路问题算法的基本思想及基本步骤
在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。
Dijkstra算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法,其时间复杂度为,虽然与重复执行Dijkstra算法n次的时间复杂度相同,但其形式上略为简单,且实际运算效果要好于前者。
Dijkstra算法基本步骤：
令：
并令：{
1、 对，求
2、 求得，使
令
3、 若则已找到到的最短路距离，否则令从中删去转1
这样经过有限次迭代则可以求出到的最短路线，可以用一个流程图来表示：

第一步 先取意即到的距离为0，而是对所赋的初值。
第二步 利用已知，根据对进行修正。
第三步 对所有修正后的求出其最小者。其对应的点是所能一步到达的店中最近的一个，由于所有。因此任何从其它点中转而到达的通路上的距离都大于直接到的距离，因此就是到的最短距离，所以在算法中令并从s中删去，若k=n则就是到的最短路线，计算结束。否则令回到第二部，计算运算，直到k=n为止。
这样每一次迭代，得到到一点的最短距离，重复上述过程直到。
Floyd算法的基本原理和实现方法为：如果一个矩阵其中表示i与j间的距离，若i与j间无路可通，则为无穷大。i 和j间的最短距离存在经过i和j间的k和不经过k两种情况，所以可以令n(n为节点数)。检查与的值，在此，与分别为目前所知的i到k与k到j的最短距离，因此，就是i到j经过k的最短距离。所以，若有就表示从i出发经k再到j的距离要比原来的i到j距离短，自然把i到j的写成。每当一个k搜索完，就是目前i到j的最短距离。重复这一过程，最后当查完所有k时，就为i到j的最短距离。
3 最短路的应用
例2 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：

L
M
N
Pa
Pe
T
L

56
35
21
51
60
M
56

21
57
78
70
N
35
21

36
68
68
Pa
21
57
36

51
61
Pe
51
78
68
51

13
T
60
70
68
61
13

解：编写程序如下：
clc,clear
a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;
a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;
a(3,4)=36;a(3,5)=68;a(3,6)=68;
a(4,5)=51;a(4,6)=61;
a(5,6)=13;
a(6,:)=0;
a=a+a';
c1=[5 1:4 6];
L=length(c1);
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
circle=c1;
sum=sum1;
c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
sum1=0;
for i=1:L-1
sum1=sum1+a(c1(i),c1(i+1));
end
if sum1<sum
sum=sum1;
circle=c1;
end
circle,sum