图论 及其原程序 MATLAB代码
需积分: 7 57 浏览量
2009-05-16
16:42:39
上传
评论
收藏 82KB PDF 举报
图论算法及其 MATLAB 程序代码
求赋权图 G = (V, E , F )中任意两点间的最短路的 Warshall-Floyd 算法：
设 A = (a
ij
)
n
×
n
为赋权图 G = (V, E , F )的矩阵, 当 v
i
v
j
∈E 时 a
ij
= F (v
i
v
j
), 否则取 a
ii
=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
k j
＜d
ij
, 则令 d
ij
= d
ik
+ d
k j
, r
ij
= k, 转向③.
③ 终止判断. 若 d
ii
＜0, 则存在一条含有顶点 v
i
的负回路, 终止; 或者 k = n 终止; 否则
令 k = k + 1, 转向②.
最短路线可由 r
ij
得到.
例 1 求图 6-4 中任意两点间的最短路.
解：用 Warshall-Floyd 算法, MATLAB 程序代码如下：
n=8;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]; % 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;end;end;end %更新 rij
k %显示迭代步数
D %显示每步迭代后的路长
R %显示每步迭代后的路径
pd=0;for i=1:n %含有负权时
if(D(i,i)<0)pd=1;break;end;end %存在一条含有顶点 vi 的负回路
if(pd)break;end %存在一条负回路, 终止程序
end %程序结束
图 6-4
剩余11页未读，继续阅读
资源评论
YEYEYEYE318
- 粉丝: 0
- 资源: 1
最新资源
- HandTrackingModule.py
- Python基于卷积神经网络的鸟类识别项目源代码，ipynb文件
- 批量将py编译为pyd文件.atbx
- Python项目-学生管理系统
- 图像处理基于matlab图像RGB三色合成分离【含Matlab源码第1发】
- verilog HDL硬件语法设计包括算术运算三人表决器Verilog的阻塞和非阻塞赋值源码例程quartus13.1工程合集
- 【文章话题分类论文】OpenAlex Topic Classification Whitepaper
- linux学习常用命令
- 功率拓扑快速参考指南-ti，TI官方出品
- 开源2023电赛国赛运动目标控制（E题）视觉部分
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
