matlab求无向图的最短路径

2023-08-07 02:29| 来源: 网络整理| 查看: 265

1 matlab图论工具箱的函数

matlab图论工具箱主要用于求最短路径，最小生成树和最大流。其常见命令如下表：

函数名功能graphallshortestpaths求图中所有顶点对之间的最短距离graphconncomp找无向图的连通分支，或有向图的强（弱）连通分支graphisdag测试有向图是否含有圈，不含圈返回1，否则返回0graphisomorphism确定两个图是否同构，同构返回1，否则返回0graphisspantree确定一个图是否生成树，是返回1，否则返回0graphmaxflow计算有向图的最大流graphminspantree在图中找最小生成树graphpred2path把前驱顶点序列变成路径的顶点序列graphshortestpath求图中指定的一对顶点间的最短距离和最短路径graphtopoorder执行有向无圈图的拓扑排序graphtraverse求从一顶点出发，所能遍历图中的顶点 2 求无向图中任意两点间的最短路径

图片如下: 在这里插入图片描述图中M2_1和M2_2之间的数字2057代表两点之间的距离。matlab中函数graphshortestpath用于求无向图任意两点间的最小距离。根据无向图，需要构造任意相邻两点之间的距离矩阵。例如：

a(1,2)=2057 ;a(1,3)=2031;

代表点M2_1和点M2_2之间的距离为2057，点M2_1和点M2_3之间的距离为2031

matlab编程实现求图中任意两点之间的距离最小值。

clc; clear; close all; % 计算任意两个之间的最小距离 sum = 0; %保存距离求和 a(1,2)=2057 ;a(1,3)=2031; %点1和点2之间的距离为2057，点1和点3之间的距离为2031 a(2,3)=1967; a(2,5)=1042; a(2,6)=1403; a(3,4)=821; a(3,5)=1115; a(4,9)=2281; a(5,8)=1905; a(6,7)=1329; a(7,8)=1666; a(8,9)=1513; a = a'; %matlab工具箱要求数据是下三角矩阵 [i,j,v] = find(a); b = sparse(i,j,v,9,9); %构造稀疏矩阵 [x,y,z] = graphshortestpath(b,1,9,'directed',false); %函数括号内1和9分别代表图中第一和第九个顶点，更改数字即可求任意两点的最小距离，x为计算得到的1和9两点间的最小距离

函数计算结果，x为5133，y为从点1到点9得到的最短距离经过的点，输出为[1 3 4 9]代表经过了第3点和第4点。

【本文地址】

公司简介

联系我们