《在图中搜索两点间的所有路径matlab编程》由会员分享，可在线阅读，更多相关《在图中搜索两点间的所有路径matlab编程（4页珍藏版）》请在金锄头文库上搜索。
1、小楼的 在图中搜索两点间的所有路径 matlab 编程在图中搜索两点间所有路径的 M 文件function possiablePaths = findPath(Graph, partialPath, destination, partialWeight)% findPath 按深度优先搜索所有可能的从 partialPath 出发到 destination 的路径，这些路径中不包含环路% Graph: 路网图，非无穷或0表示两节点之间直接连通，矩阵值就为路网权值% partialPath: 出发的路径，如果 partialPath 就一个数，表示这个就是起始点% destination: 目标
2、节点% partialWeight: partialPath 的权值，当 partialPath 为一个数时，partialWeight 为0pathLength = length(partialPath);lastNode = partialPath(pathLength); %得到最后一个节点nextNodes = find(0Graph(lastNode,:) %根据 Graph 图得到最后一个节点的下一个节点GLength = length(Graph);possiablePaths = ;if lastNode = destination% 如果 lastNode 与目标节点相等，则
3、说明 partialPath 就是从其出发到目标节点的路径，结果只有这一个，直接返回possiablePaths = partialPath;possiablePaths(GLength + 1) = partialWeight;return;elseif length( find( partialPath = destination ) ) = 0return;end%nextNodes 中的数一定大于0,所以为了让 nextNodes(i)去掉，先将其赋值为0for i=1:length(nextNodes)if destination = nextNodes(i)%输出路径tmpPath
4、 = 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) ) ) = 0nextNodes(i) =
5、0;endendnextNodes = 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, tmpPs
6、bPaths);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.00001.0
7、000 2.0000 4.0000 5.0000 6.0000 7.0000 0 146.80001.0000 2.0000 4.0000 6.0000 7.0000 0 0 136.80001.0000 2.0000 5.0000 4.0000 3.0000 7.0000 0 142.00001.0000 2.0000 5.0000 4.0000 6.0000 7.0000 0 133.80001.0000 2.0000 5.0000 6.0000 7.0000 0 0 121.80001.0000 2.0000 5.0000 6.0000 4.0000 3.0000 7.0000 158.00001.0000 3.0000 7.0000 0 0 0 0 115.00001.0000 3.0000 4.0000 2.0000 5.0000 6.0000 7.0000 159.80001.0000 3.0000 4.0000 5.0000 6.0000 7.0000 0 134.80001.0000 3.0000 4.0000 6.0000 7.0000 0 0 124.8000
