Matlab 图论最短路问题模型代码
2023-09-11 14:22:04 时间
最短路问题的基本内容
最短路问题研究的是,在一个点与点之间连接形成的网络图中,对应路径赋予一定的权重(可以理解为两点之间的距离),计算任意两点之间如何和走,路径最短的问题。在这里的距离可以理解成各种两点之间某种任务的开销。
模型调用
解决最短路问题,一般可采取 dijkstra
或者floyd
这两种模型,模型调用形式如下:
[mydist,mypath]=mydijkstra(a,sb,db) % dijkstra模型
[mydist,mypath]=myfloyd(a,sb,db) % floyd模型
其中,
- a 为邻接矩阵
- sb 为起点标号
- db 为终点标号
- mydist 为最短路径长度
- mypath 为最短路径
模型完整代码
Dijkstra 模型代码
function [mydistance,mypath]=mydijkstra(a,sb,db);
% 输入:a—邻接矩阵,a(i,j)是指i到j之间的距离,可以是有向的
% sb—起点的标号, db—终点的标号
% 输出:mydistance—最短路的距离, mypath—最短路的路径
n=size(a,1); visited(1:n) = 0;
distance(1:n) = inf; distance(sb) = 0; %起点到各顶点距离的初始化
visited(sb)=1; u=sb; %u为最新的P标号顶点
parent(1:n) = 0; %前驱顶点的初始化
for i = 1: n-1
id=find(visited==0); %查找未标号的顶点
for v = id
if a(u, v) + distance(u) < distance(v)
distance(v) = distance(u) + a(u, v); %修改标号值
parent(v) = u;
end
end
temp=distance;
temp(visited==1)=inf; %已标号点的距离换成无穷
[t, u] = min(temp); %找标号值最小的顶点
visited(u) = 1; %标记已经标号的顶点
end
mypath = [];
if parent(db) ~= 0 %如果存在路!
t = db; mypath = [db];
while t ~= sb
p = parent(t);
mypath = [p mypath];
t = p;
end
end
mydistance = distance(db);
Floyd 模型代码
function [dist,mypath]=myfloyd(a,sb,db);
% 输入:a—邻接矩阵,元素(aij)是顶点i到j之间的直达距离,可以是有向的
% sb—起点的标号;db—终点的标号
% 输出:dist—最短路的距离;% mypath—最短路的路径
n=size(a,1); path=zeros(n);
for k=1:n
for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=k;
end
end
end
end
dist=a(sb,db);
parent=path(sb,:); %从起点sb到终点db的最短路上各顶点的前驱顶点
parent(parent==0)=sb; %path中的分量为0,表示该顶点的前驱是起点
mypath=db; t=db;
while t~=sb
p=parent(t); mypath=[p,mypath];
t=p;
end
案例演示
对于上面的网络图,求解从 A 到 D 的最短路径。
整理邻接矩阵
首先整理出点与点之间连接关系,得出邻接矩阵。
假设点的排序为:
点位 | A | B1 | B2 | C1 | C2 | C3 | D |
---|---|---|---|---|---|---|---|
序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
整理出 7*7 邻接矩阵:
完整代码
% 构造邻接矩阵
a = zeros(7);
a(1,2) = 2; a(1,3) = 4;
a(2,4) = 3; a(2,5) = 3; a(2,6) = 1;
a(3,4) = 2; a(3,5) = 3; a(3,6) = 1;
a(4,7) = 1;
a(5,7) = 3;
a(6,7) = 4;
a = a + a';
a(a==0) = inf; % 零元素换成inf
a(eye(7,7)==1)=0; % 对角线换成 0
[mydist1,mypath1]=mydijkstra(a,1,7) % dijkstra模型求解
[mydist2,mypath2]=myfloyd(a,1,7) % floyd 模型求解
运行结果
mydist1 =
6
mypath1 =
1 2 4 7
mydist2 =
6
mypath2 =
1 2 4 7
将序号还原成点位,即最短路径为 A → B1 → C1 → D
相关文章
- Matlab中set函数的使用
- 【转】EM算法MATLAB代码及详细注解
- 2021年春季学期-信号与系统-第五次作业参考答案-第十一移小题—MATLAB
- 【Efficient-Net】基于Efficient-Net效率网的目标识别算法的MATLAB仿真——详细版
- 【MATLAB教程案例97】基于GA遗传优化的CNN卷积神经网络最优训练参数搜索matlab仿真
- 【MATLAB教程案例82】matlab在大学数学中的应用——概率统计
- 【MATLAB教程案例61】使用matlab实现基于ResNet残差网络的数据分类仿真分析
- 【MATLAB教程案例52】SVM支持向量机学习——使用matlab实现基于SVM的数据二分类
- 【MATLAB教程案例49】三维点云数据ICP配准算法的matlab仿真学习
- 【MATLAB教程案例44】通过matlab学习三维曲面的建模,颜色,透明度,动态变化等——以海浪曲面函数为例
- 【MATLAB教程案例40】语音信号的共振峰频率倒谱法估计matlab仿真学习
- 【MATLAB教程案例31】基于matlab的人脸检测相关算法的仿真与分析——肤色模型与形态学图像处理方法
- 2.MATLAB安装
- 【MATLAB教程案例11~20总结】优化类算法matlab仿真经验和技巧总结
- 【MATLAB教程案例9】信道编译码之turbo编码译码算法matlab误码率仿真
- 【MATLAB教程案例8】基于LS算法的OFDM调制解调系统信道估计和均衡算法的matlab仿真
- 【MATLAB教程案例5】常见无线通信信道的matlab模拟和仿真分析——自由空间损耗模型,Okumura-Hata模型以及COST231 Hata模型
- 【FPGA教程案例91】机器视觉2——通过FPGA实现基于肤色模型的人脸检测,使用MATLAB辅助测试
- MATLAB 数据分析方法(第2版)1.5 M文件与编程
- 【Matlab 六自由度机器人】关于灵活工作空间与可达工作空间的理解(附MATLAB推导代码)
- 【Matlab算法】MATLAB求解背包问题(附MATLAB代码)
- 【Matlab算法】G-N法求解非线性最小二乘优化问题(附G-N法MATLAB代码)
- MatLab教程之使用Excel和MATLAB求解工程中的线性和非线性方程
- 导出CCS3.3数据及使用matlab处理的方法
- Matlab 模拟退火算法模型代码
- [原创] Matlab 指派问题模型代码
- Matlab 整数线性规划问题模型代码