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