| 查看: 3669 | 回复: 2 | ||
[求助]
MATLAB 编程搜索图中两点间的所有路径
|
|
有各节点的权值矩阵，要找出图中起点和终点的所有路径 问题一：程序的清晰、具体的思路是什么？初学MATLAB，好难理清这个程序一步步是怎么算的 问题二：矩阵超过10X10之后，就运行不出来 程序如下： function possiablePaths = findPath(Graph, partialPath, destination, partialWeight) % findPath按深度优先搜索所有可能的从partialPath出发到destination的路径，这些路径中不包含环路 % Graph: 路网图，非无穷或0表示两节点之间直接连通，矩阵值就为路网权值 % partialPath: 出发的路径，如果partialPath就一个数，表示这个就是起始点 % destination: 目标节点 % partialWeight: partialPath的权值，当partialPath为一个数时，partialWeight为0 pathLength = length(partialPath); lastNode = partialPath(pathLength); %得到最后一个节点 nextNodes = find(0<Graph(lastNode,  & Graph(lastNode,<inf); %根据Graph图得到最后一个节点的下一个节点GLength = length(Graph); possiablePaths = []; if lastNode == destination % 如果lastNode与目标节点相等，则说明partialPath就是从其出发到目标节点的路径，结果只有这一个，直接返回 possiablePaths = partialPath; possiablePaths(GLength + 1) = partialWeight; return; elseif length( find( partialPath == destination ) ) ~= 0 return; end %nextNodes中的数一定大于0,所以为了让nextNodes(i)去掉，先将其赋值为0 for i=1:length(nextNodes) if destination == nextNodes(i) %输出路径 tmpPath = cat(2, partialPath, destination); %串接成一条完整的路径 tmpPath(GLength + 1) = partialWeight + Graph(lastNode, destination); %延长数组长度至GLength+1, 最后一个元素用于存放该路径的总路阻 possiablePaths( length(possiablePaths) + 1 , : ) = tmpPath; nextNodes(i) = 0; elseif length( find( partialPath == nextNodes(i) ) ) ~= 0 nextNodes(i) = 0; end end nextNodes = nextNodes(nextNodes ~= 0); %将nextNodes中为0的值去掉，因为下一个节点可能已经遍历过或者它就是目标节点 for i=1:length(nextNodes) tmpPath = cat(2, partialPath, nextNodes(i)); tmpPsbPaths = findPath(Graph, tmpPath, destination, partialWeight + Graph(lastNode, nextNodes(i))); possiablePaths = cat(1, possiablePaths, tmpPsbPaths); end %输入桐乡到富阳的高速公路网络图的边权矩阵 a=[0,62,66,inf,inf,inf,inf; 62,0,inf,25,11,inf,inf; 66,inf,0,9,inf,inf,49; inf,25,9,0,11,14,inf; inf,11,inf,11,0,13,inf; inf,inf,inf,14,13,0,35.8; inf,inf,49,inf,inf,35.8,0;]; %调用搜索图中任意两点间所有路径的M文件 findPath(a, 1, 7, 0) 程序来源http://www.ilovematlab.cn/thread-212175-1-1.html 或者http://www.360doc.com/content/11/0818/21/2617151_141536552.shtml |
回复此楼» 猜你喜欢
292求调剂
已经有6人回复
-
化学工程085602 305分求调剂
已经有7人回复
-
332求调剂
已经有5人回复
-
材料求调剂
已经有4人回复
-
303求调剂
已经有5人回复
-
334分 一志愿武理-080500 材料求调剂
已经有4人回复
-
求调剂
已经有3人回复
-
299求调剂
已经有3人回复
-
299求调剂
已经有8人回复
-
316求调剂
已经有8人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 两点间所有路径的算法，并且求出各情况路径的大小
已经有5人回复
- 如何实现matlab在一个图里以同一个横坐标画两个图
已经有5人回复
- matlab如何得到图中点对应元素的的位置，请具体点。谢谢。
已经有9人回复
- matlab中如何用regress实现批量回归并出图
已经有8人回复
- Matlab三维图中如何实现x，y坐标名称与各自的坐标轴平行？
已经有4人回复
- 求助此图的ostu方法分割图像的matlab编程，急急急，金币不是问题啊！
已经有8人回复
- Matlab 实现DGGE电泳图谱的 泳道多样性指数，相似性指数，泳道聚类分析
已经有26人回复
- matlab实现图像压缩是的压缩率怎么求
已经有5人回复
- 【分享】算法大全一到三十章完全版(matlab实现，数学建模中很实用)【已搜无重复】
已经有1059人回复
- 请问如何用Matlab编程做这个图？谢谢大家！
已经有5人回复
- 如何用matlab软件或者用C及C++自己手工编程寻找转折点
已经有12人回复
- MATLAB 编程求解普通实验数据时间序列的最大李雅普诺夫指数！！！
已经有12人回复
- 【求助】vb与matlab混合编程时图形显示窗口中，怎样使图形比窗口小一些？
已经有3人回复
- 【求助】求算法，两点间距离问题
已经有7人回复
2楼2013-11-11 10:40:14
3楼2013-11-11 12:25:03
5