matlab求无向图的最短路径 | 您所在的位置:网站首页 › 图中的路径 › matlab求无向图的最短路径 |
1 matlab图论工具箱的函数
matlab图论工具箱主要用于求最短路径,最小生成树和最大流。 其常见命令如下表: 函数名功能graphallshortestpaths求图中所有顶点对之间的最短距离graphconncomp找无向图的连通分支,或有向图的强(弱)连通分支graphisdag测试有向图是否含有圈,不含圈返回1,否则返回0graphisomorphism确定两个图是否同构,同构返回1,否则返回0graphisspantree确定一个图是否生成树,是返回1,否则返回0graphmaxflow计算有向图的最大流graphminspantree在图中找最小生成树graphpred2path把前驱顶点序列变成路径的顶点序列graphshortestpath求图中指定的一对顶点间的最短距离和最短路径graphtopoorder执行有向无圈图的拓扑排序graphtraverse求从一顶点出发,所能遍历图中的顶点 2 求无向图中任意两点间的最短路径图片如下: 代表点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点。 |
CopyRight 2018-2019 实验室设备网 版权所有 |