诚一网站推广,wordpress文章自动添加超链接,阿里云服 WordPress,深圳附近做个商城网站哪家公司便宜点目录图的简介无向图#xff08;Graph#xff09;生成带权邻接矩阵求两点最短路径有向图#xff08;Digraph#xff09;生成带权邻接矩阵求最短路径图的简介
图是拓扑学中的一个重要概念#xff0c;分为无向图和有向图两种。图有两个重要属性#xff0c;即点#xff08;…
目录图的简介无向图Graph生成带权邻接矩阵求两点最短路径有向图Digraph生成带权邻接矩阵求最短路径图的简介
图是拓扑学中的一个重要概念分为无向图和有向图两种。图有两个重要属性即点Node和边Edge。在图的概念中我们只关心点和边的连接关系而并不关系他们在图中的相对位置。 由点和边连接的图中将边赋予一定的权重就可以将图转换为各种问题例如TSP旅行商问题、Shortest Path最短路径问题。本文先介绍如何借助图以及赋予的边的权值生成带权邻接矩阵再介绍利用图求两点之间最短路径的求法。
无向图Graph
生成带权邻接矩阵
先介绍根据以下无向图生成带权邻接矩阵的方法 假设我们已经知道了每条边的权重红色标定该图中有11个点如果挨个写出需要121个元素对于此图已经非常繁琐。因此我给大家提供一种简单的方法只需要写出图中标定权值的边即可达到目的。书写规则如下 A→A标定权值是0 若A→B没有路径可以到达标定权值为0 若A→C有路径可以到达根据建模需要标定权值 这样我们在手动书写时仅需要写出非0边的权重即可每条边只需要书写一次书写方式如下
Wzeros(11);
W(1,2)2;
W(1,4)1;
W(1,3)8;
W(2,3)6;
W(2,5)1;
W(3,4)7;
W(3,5)5;
W(3,6)1;
W(3,7)2;
W(4,7)9;
W(5,6)3;
W(5,8)2;
W(5,9)9;
W(6,7)4;
W(6,9)6;
W(7,9)3;
W(7,10)1;
W(8,9)7;
W(8,11)8;
W(9,10)1;
W(9,11)2;
W(10,11)4;由于本例中为无向图因此生成的矩阵总满足W(i,j)W(j,i)所以利用以下代码书写另一半
nsize(W,1);
for i1:nfor ji:nW(j,i)W(i,j);%次对角线分隔的下三角部分根据上三角部分对称end
end
Ggraph(W,upper);%根据带权邻接矩阵生成无向图
plot(G,EdgeLabel,G.Edges.Weight)
title(标定权重的无向图)自动绘图效果如下 带权邻接矩阵W如下 如果要将平时我们认为的不能到达的路径之间权重设定为Inf也很容易不过在Matlab内置的函数shortestpath中认为权重0即不设路径
求两点最短路径 格式[path,distance]shortestpath(G,1,6) path返回的是路径经过的点distance是该路径的长度 例如在工作区输入
[path,distance]shortestpath(G,1,6)显示如下 对照我们绘制的无向图也很容易手动验证最短路径即1→2→5→6最短路径的距离2136。
有向图Digraph
生成带权邻接矩阵
有向图示例如下 创建一个数组每一列依次保存起始点出发点以及带权。按照和无向图同样的方法对每条边书写带权
W[1 2 10;1 4 10;1 8 1;2 3 10;2 7 1;3 4 10;3 6 1;4 5 1;5 6 12;5 8 12;6 7 12;7 8 12;];用类似的方法生成有向图如下
startpointsW(:,1);%起始点集合
endpointsW(:,2);%结束点集合
weightsW(:,3);%对应起始点和结束点的边权重
Gdigraph(startpoints,endpoints,weights);%生成有向图
plot(G,EdgeLabel,weights,layout,force,Edgecolor,red)%画出有向图效果如下
求最短路径
在工作区求取最短路径格式如下 格式 [path,distance]shortestpath(G,s,t) 得到的结果如下 在此需要说明的和无向图的区别是在这里我们只有起始点的点数比终点点数小才有路径否则没有因此如果按照如下条件调用则会得到空集利用这一个特点可以在程序中增加条件加以排除。 if distanceInf 或 if path[] [path,distance]shortestpath(G,8,2)希望本文对您有帮助谢谢阅读
