没有合适的资源?快使用搜索试试~ 我知道了~
用matlab实现寻找最短路.docx
0 下载量 40 浏览量
2022-11-15
12:13:10
上传
评论
收藏 24KB DOCX 举报
温馨提示
试读
12页
用matlab实现寻找最短路.docx
资源推荐
资源详情
资源评论
用 matlab 寻找赋权图中的最短路中的应用
1 引言
图论是应用数学的一个分支,它的概念和结果来源都非常广泛,最早起源于一些数学游
戏的难题研究,如欧拉所解决的格尼斯堡七桥问题,以及在民间广泛流传的一些游戏的难题,
如迷宫问题,博弈问题等。这些古老的难题,吸引了很多学者的注意。
1847 年,图论应用于分析电路网络,这是它最早应用于工程科学,以后随着科学的发
展,图论在解决运筹学,网络理论,信息论,控制论,博弈论以及计算机科学等各个领域的
问题时,发挥出很大的作用。在实践中,图论已成为解决自然科学,工程技术,社会科学,
军事等领域中许多问题的有力工具之一。
最短路问题是图论理论中的经典问题,寻找最短路径就是在指定网络中两节点间找一条
距离最小的路。
2 最短路
2.1 最短路的定义(short-path problem)
对 最 短 路 问 题 的 研 究 早 在 上 个 世 纪 60 年 代 以 前 就 卓 有 成 效 了 , 其中对赋权图
( )
0
ij
w ³
的有效算法是由荷兰著名计算机专家 E.W.Dijkstra 在 1959 年首次提出的,该算法能
够解决两指定点间的最短路,也可以求解图 G 中一特定点到其它各顶点的最短路。后来海斯
在 Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短
路问题。因此由 Ford 提出了 Ford 算法,它能有效地解决含有负权的最短路问题。但在现实生
活中,我们所遇到的问题大都不含负权,所以我们在
( )
0
ij
w ³
的情况下选择 Dijkstra 算法。
若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是
源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解
决的典型问题之 一,它不仅 可以直接应 用于 解决生 产实际的许 多问题,如 管路铺设、
线路安装、厂区布局和设备更新等,而且经常被作为一个基本的工具,用于解决其他
的做优化问题。
定义 1:若图 G=G(V,E)中个边[v
i
,v
j
]都赋有一个实数 w
ij
,则称这样的图 G 为
赋权图,w
ij
称为边[v
i
,v
j
]上的权。
定 义 2 : 给 定 一 个 赋 权 有 向 图 , 即 给 一 个 有 向 图 D= ( V,A ), 对 每 一 个 弧 a=
(v
i
,v
j
),相应地有权 w(a)=w
ij
,又给定 D 中的两个顶点 v
s
,v
t
。设 P 是 D 中从 v
s
到
v
t
的一条路,定义路 P 的权是 P 中所有弧的权之和,记为 w(P)。最短路问题就是要在所有
从 v
s
到 v
t
的路中,求一条权最小的路,即求一条从 v
s
到 v
t
的路 P
0
,使 w(P
0
)=
P
min
w
(P)式中对 D 中所有从 v
s
到 v
t
的路 P 最小,称 P
0
是从 v
s
到 v
t
的最短路。
2.2 最短路问题算法的基本思想及其基本步骤
在求解网络图上节点间最短路径的方法中,目前国内外一致公认的比较好的算法有
Dijkstra 和 Floyd 算法。这两种算法,网络被抽象为一个图论中定义的有向图或无向图,并利
用图的节点邻接矩阵记录点的关联信息。在进行图的遍历搜索最短路径时,以该矩阵为基础
不断进行目标值的最小性判别,知道获得最后的优化路径。鉴于课本使用 Dijkstra 算法,下
面用 Floyd 算法进行计算:
设 A=(a)
n*n
为赋权图 G=(V,E,F)的矩阵,当 V
i
V
j
∈E 时,a
ij
=F(v
i
,v
j
),否则,
取 a
ij
=0,a
ij
=+∞(i≠j),d
ij
表示从 v
i
到 v
j
的点的距离,r
ij
表示从 v
i
到 v
j
的点的最短路中的
一个点的编号。
① 赋初值。对所有 i,j,d
ij
= a
ij
,r
ij
=j,k=1,转向②;
② 更新 d
ij
,r
ij
,对所有 i,j,若 d
ik
+ d
kj
< d
ij
,则令 d
ij
= d
ik
+ d
kj
,r
ij
=k,转向;
③ 终止判断。若 d
ij
<0,则存在一条含有顶点 v
i
的负回路,终止;或者 k=n,终止;否则,
另 k=k+1,转向②。
最短路线可由 r
ij
得到。
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)
剩余11页未读,继续阅读
资源评论
Mmnnnbb123
- 粉丝: 692
- 资源: 8万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功