偶看新闻沈阳方特乐园:引用 在图中搜索两点间的所有路径matlab编程
来源：百度文库 编辑：偶看新闻 时间：2024/04/28 20:12:16
% findPath按深度优先搜索所有可能的从partialPath出发到destination的路径，这些路径中不包含环路
% Graph: 路网图，非无穷或0表示两节点之间直接连通，矩阵值就为路网权值
% partialPath: 出发的路径，如果partialPath就一个数，表示这个就是起始点
% destination: 目标节点
% partialWeight: partialPath的权值，当partialPath为一个数时，partialWeight为0
pathLength = length(partialPath);
lastNode = partialPath(pathLength); %得到最后一个节点
nextNodes = find(0
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)
输出结果：
ans =
1.0000 2.0000 4.0000 3.0000 7.0000 0 0 145.0000
1.0000 2.0000 4.0000 5.0000 6.0000 7.0000 0 146.8000
1.0000 2.0000 4.0000 6.0000 7.0000 0 0 136.8000
1.0000 2.0000 5.0000 4.0000 3.0000 7.0000 0 142.0000
1.0000 2.0000 5.0000 4.0000 6.0000 7.0000 0 133.8000
1.0000 2.0000 5.0000 6.0000 7.0000 0 0 121.8000
1.0000 2.0000 5.0000 6.0000 4.0000 3.0000 7.0000 158.0000
1.0000 3.0000 7.0000 0 0 0 0 115.0000
1.0000 3.0000 4.0000 2.0000 5.0000 6.0000 7.0000 159.8000
1.0000 3.0000 4.0000 5.0000 6.0000 7.0000 0 134.8000
1.0000 3.0000 4.0000 6.0000 7.0000 0 0 124.8000