求最短路径（graphshortestpath），求最小生成树（minspantree）
文章目录
-
- 求最短路径（graphshortestpath），求最小生成树（minspantree）
-
- 1、最短路径问题
- 2、最小生成树
1、最短路径问题
最短路径：从图中的某个顶点出发，到达另外一个顶点的所经过的边的权重之和最小的一条路径。
- 图：边和节点组成的结构，在数学建模中例如本题中道路和城市。
- 边：带有方向的是有向图，否则为无向图。
- 权重：每条边都有与之对应的值，本题中边道路，边的权重就是道路长度，当然是越小越好。
MATLAB求解最短路径：**Dijkstra算法，或MATLAB的graphshortestpath**函数
例：
%sparse生成稀疏矩阵，也就是除了注明的几个元素外，其余都是0
%spare里第一个和第二个矩阵相同位置的元素值就是非零元素的索引
%非零元素的值
%w是每条边的权值
w=[10,5,2,1,4,6,7,3,9,2]
DG = sparse([1,1,2,2,3,4,4,5,5,5],[2,5,5,3,4,3,1,2,3,4],w)
% 没有就默认为零，这样快速生成一个稀疏矩阵
生成
% dist是最短路径的值, path是最短路径的节点顺序
% pred是到每一个节点的最短路径的终点前一个节点
% 如果求节点1到其他所有节点的最短路径呢?
[dist,path,pred] = graphshortestpath(DG,1,3) %后面的数字参数是起点和终点，然后计算最短路径
显示
% biograph生成图对象; view显示该图
point_name =["城市1", "城市2", "城市3","城市4", "城市5"]
h = view(biograph(DG,point_name, 'Showweights', 'on'))
优化
% 将最短路径的节点和边缘标记为红色并增加线宽
% getedgesbynodeid得到图h的指定边的句柄
% 第一个参数是图，第二个是边的出点，第三个是边的入点%句柄确保能找到对应的东西
% get查询图的属性，h.Nodes(path), 'ID'得到图h中最短路径的
% set函数设置图形属性
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID')); %选取最短路径，并找到ID
set(edges,'LineColor', [1 0 0])% RGB数值，红绿蓝
set(edges,'Linewidth',2)
最终结果：
2、最小生成树
-
最短路径的区别：最短路径是针对某一顶点作为起点而言的，最小生成树是所有顶点连通且总路径最小。
-
最小生成树的求解:
MATLAB的
minspantree函数求解最小生成树，还有克鲁斯卡尔（Kruskal）算法，和普利姆（Prim）算法。
minspantree函数演示：
s = [1,1,2,2,3,3,4,4,4,5];
t = [2,3,4,5,4,7,5,6,7,6];
weights = [50,60,65,40,52,45,50,30,42,70];
%生成无向图，其中s和t对应元素代表着边，weights是权值
G= graph(s,t,weights);
%求出最小生成树，得到的T包含最小生成树的节点和对应边的权
T= minspantree(G);
服务器托管网
% p = plot(G)就能把图片展现出来，后面是为了美观设置字体等
p = plot(G, 'EdgeLabel ',G.Edges.weight,"MarkerSize",8,'NodeFontSize',16,'EdgeFontSize',16)
%highlight突出显示绘制的图中的节点和边
highlight(p,T,'EdgeColor','red',"Linewidth",3)
在上述的代码中，T里面存的就是最小的生成树，而后续的操作只是为了更加的美观。
运行结果：
服务器托管，北京服务器托管，服务服务器托管网器租用 http://www.fwqtg.net
空间包围检测在计算机图形学、虚拟仿真、工业生产等有着广泛的应用。 现代煤矿开采过程中，安全一直是最大的挑战之一。地质空间中存在诸多如瓦斯积聚、地质构造异常、水文条件不利等隐蔽致灾因素，一旦被触发，可能引发灾难性的后果。因此在安全生产过程中有效的管理和规避各隐蔽…
