用matlab实现寻找最短路.docx

用matlab寻找赋权图中的最短路中的应用

1 引言

图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。
1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。

2 最短路

2.1 最短路的定义（short-path problem）
对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的情况下选择Dijkstra算法。
若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。

定义1：若图G=G（V，E）中个边[vi ,vj]都赋有一个实数wij ，则称这样的图G为赋权图，wij 称为边[vi ,vj]上的权。
定义2：给定一个赋权有向图，即给一个有向图D=（V,A），对每一个弧a=（vi ,vj），相应地有权w（a）=wij，又给定D中的两个顶点vs ，vt 。设P是D中从vs 到vt 的一条路，定义路P的权是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从vs到vt 的路中，求一条权最小的路，即求一条从vs到vt 的路P0 ，使w（P0）=w（P）式中对D中所有从vs到vt 的路P最小，称P0 是从vs到vt 的最短路。

2.2 最短路问题算法的基本思想及其基本步骤

在求解网络图上节点间最短路径的方法中，目前国内外一致公认的比较好的算法有Dijkstra和Floyd算法。这两种算法，网络被抽象为一个图论中定义的有向图或无向图，并利用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，知道获得最后的优化路径。鉴于课本使用Dijkstra算法，下面用Floyd算法进行计算：
设A=（a）n*n 为赋权图G=（V，E，F）的矩阵，当ViVj ∈E时，aij =F（vi，vj），否则，取aij =0，aij =+∞（i≠j），dij 表示从vi到vj 的点的距离，rij 表示从vi到vj 的点的最短路中的一个点的编号。
① 赋初值。对所有i，j，dij = aij ，rij =j，k=1，转向②；
② 更新dij ，rij ，对所有i，j，若dik + dkj < dij ,则令dij = dik + dkj ，rij =k，转向；
③ 终止判断。若dij <0,则存在一条含有顶点vi的负回路，终止；或者k=n，终止；否则，另k=k+1，转向②。
最短路线可由rij得到。

2.3 用matlab程序实现上述算法

编写程序函数程序如下：

function f=shortpath(n,A)
clear;
n=input('请输入矩阵的阶n=');
A=input('请输入赋权图对应的n阶矩阵A='); % 顶点之间不通时，用inf表示（MATLAB中，inf表示无穷）
D=A; %赋初值
for(i=1:n)
for(j=1:n)
R(i,j)=j;
end;
end %赋路径初值
for(k=1:n)
for(i=1:n)
for(j=1:n)
if(D(i,k)+D(k,j)<D(i,j))
D(i,j)=D(i,k)+D(k,j); %更新dij
R(i,j)=k; %更新rij
end;
end;
end
k %显示迭代步数
D %显示每步迭代后的路长
R %显示每步迭代后的路径
pd=0;
for(i=1:n) %含有负权
if(D(i,j)<0)
pd=1;
break;
end;
end %存在一条含有顶点的vi的负回路
if(pd)
break;
end %存在一条负回路，终止程序
end %程序结束

下面用一个实际的例子进行一下函数实际运算：
例：求解下赋权图中任意两点中的最短路。
V1 6 V4
2 6 5 3 8
V0 8 V2 1 V5 6 v7
1 7 2 4 3
V3 9 V5
用matlab函数运行以后，运行结果如下：

请输入矩阵的阶n=8
请输入赋权图对应的n阶矩阵A=[0 2 8 1 inf inf inf inf;2 0 6 inf 1 inf inf inf;8 6 0 7 5 1 2 inf;1 inf 7 0 inf inf 9 inf;inf 1 5 inf 0 3 inf 8;inf inf 1 inf 3 0 4 6;inf inf 2 9 inf 4 0 3;inf inf inf inf 8 6 3 0]

k =1

D =
0 2 8 1 Inf Inf Inf Inf
2 0 6 3 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 Inf Inf 9 Inf
Inf 1 5 Inf 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0

R =
1 2 3 4 5 6 7 8
1 2 3 1 5 6 7 8
1 2 3 4 5 6 7 8
1 1 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

k =2

D =
0 2 8 1 3 Inf Inf Inf
2 0 6 3 1 Inf Inf Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 Inf 9 Inf
3 1 5 4 0 3 Inf 8
Inf Inf 1 Inf 3 0 4 6
Inf Inf 2 9 Inf 4 0 3
Inf Inf Inf Inf 8 6 3 0

R =
1 2 3 4 2 6 7 8
1 2 3 1 5 6 7 8
1 2 3 4 5 6 7 8
1 1 3 4 2 6 7 8
2 2 3 2 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

k =3

D =
0 2 8 1 3 9 10 Inf
2 0 6 3 1 7 8 Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 8 9 Inf
3 1 5 4 0 3 7 8
9 7 1 8 3 0 3 6
10 8 2 9 7 3 0 3
Inf Inf Inf Inf 8 6 3 0

R =
1 2 3 4 2 3 3 8
1 2 3 1 5 3 3 8
1 2 3 4 5 6 7 8
1 1 3 4 2 3 7 8
2 2 3 2 5 6 3 8
3 3 3 3 5 6 3 8
3 3 3 4 3 3 7 8
1 2 3 4 5 6 7 8

k =4

D =
0 2 8 1 3 9 10 Inf
2 0 6 3 1 7 8 Inf
8 6 0 7 5 1 2 Inf
1 3 7 0 4 8 9 Inf
3 1 5 4 0 3 7 8
9 7 1 8 3 0 3 6
10 8 2 9 7 3 0 3
Inf Inf Inf Inf 8 6 3 0

R =
1 2 3 4 2 3 3 8
1 2 3 1 5 3 3 8
1 2 3 4 5 6 7 8
1 1 3 4 2 3 7 8
2 2 3 2 5 6 3 8
3 3 3 3 5 6 3 8
3 3 3 4 3 3 7 8
1 2 3 4 5 6 7 8

k =5

D =
0 2 8 1 3 6 10 11
2 0 6 3 1 4 8 9
8 6 0 7 5 1 2 13
1 3 7 0 4 7 9 12
3 1 5 4 0 3 7 8
6 4 1 7 3 0 3 6
10 8 2 9 7 3 0 3
11 9 13 12 8 6 3 0

R =
1 2 3 4 2 5 3 5
1 2 3 1 5 5 3 5
1 2 3 4 5 6 7 5
1 1 3 4 2 5 7 5
2 2 3 2 5 6 3 8
5 5 3 5 5 6 3 8
3 3 3 4 3 3 7 8
5 5 5 5 5 6 7 8

k = 6

D =
0 2 7 1 3 6 9 11
2 0 5 3 1 4 7 9
7 5 0 7 4 1 2 7
1 3 7 0 4 7 9 12
3 1 4 4 0 3 6 8
6 4 1 7 3 0 3 6
9 7 2 9 6 3 0 3
11 9 7 12 8 6 3 0

R =
1 2 6 4 2 5 6 5
1 2 6 1 5 5 6 5
6 6 3 4 6 6 7 6
1 1 3 4 2 5 7 5
2 2 6 2 5 6 6 8
5 5 3 5 5 6 3 8
6 6 3 4 6 3 7 8
5 5 6 5 5 6 7 8

k =7

D =
0 2 7 1 3 6 9 11
2 0 5 3 1 4 7 9
7 5 0 7 4 1 2 5
1 3 7 0 4 7 9 12
3 1 4 4 0 3 6 8
6 4 1 7 3 0 3 6
9 7 2 9 6 3 0 3
11 9 5 12 8 6 3 0

R =
1 2 6 4 2 5 6 5
1 2 6 1 5 5 6 5
6 6 3 4 6 6 7 7
1 1 3 4 2 5 7 5
2 2 6 2 5 6 6 8
5 5 3 5 5 6 3 8
6 6 3 4 6 3 7 8
5 5 7 5 5 6 7 8

k = 8

D =
0 2 7 1 3 6 9 11
2 0 5 3 1 4 7 9
7 5 0 7 4 1 2 5
1 3 7 0 4 7 9 12
3 1 4 4 0 3 6 8
6 4 1 7 3 0 3 6
9 7 2 9 6 3 0 3
11 9 5 12 8 6 3 0

R =
1 2 6 4 2 5 6 5
1 2 6 1 5 5 6 5
6 6 3 4 6 6 7 7
1 1 3 4 2 5 7 5
2 2 6 2 5 6 6 8
5 5 3 5 5 6 3 8
6 6 3 4 6 3 7 8
5 5 7 5 5 6 7 8

注：上例中是用一个无向赋权图，对与有向赋权图只需要把反向的定义为无穷大（在matlab中即用inf代替不能到达的情况），一样可以调用上述函数程序进行运算。

3 最短路的实际应用

● 最短路问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输路线等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。

● 最短路问题在实际中还常用于汽车导航系统以及各种应急系统等（110报警、119火警以及120医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间最短。利用最短路还需要实际计算出前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。

● 根据现在发展的要求，在城乡一体化的总体思路中，为实现农村村村通的目标，针对农村地理分布，进行合理规划，对与优化农村交通网络，促进农村发展有重要的内容。

4 结语

本文将最短路理论与实际相联系，尤其是对与当前热点问题的应用，具有很重要的意义。将实际生活中出现的安全隐患尽量降低。同时也凸显出学习与应用最短路原理的重要性。要在平时的生活中，注意学习中的相关联系，那样会对学习产生更大的兴趣。

- 11 -