function possiablePaths = findPath(Graph, partialPath, destination, partialWeight)
% findPath按深度優(yōu)先搜索所有可能的從partialPath出發(fā)到destination的路徑，這些路徑中不包含環(huán)路
% Graph: 路網(wǎng)圖，非無(wú)窮或0表示兩節(jié)點(diǎn)之間直接連通，矩陣值就為路網(wǎng)權(quán)值
% partialPath: 出發(fā)的路徑，如果partialPath就一個(gè)數(shù)，表示這個(gè)就是起始點(diǎn)
% destination: 目標(biāo)節(jié)點(diǎn)
% partialWeight: partialPath的權(quán)值，當(dāng)partialPath為一個(gè)數(shù)時(shí)，partialWeight為0
pathLength = length(partialPath);
lastNode = partialPath(pathLength); %得到最后一個(gè)節(jié)點(diǎn)
nextNodes = find(0<Graph(lastNode,:) & Graph(lastNode,:)<inf); %根據(jù)Graph圖得到最后一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
GLength = length(Graph);
possiablePaths = [];

if lastNode == destination
 % 如果lastNode與目標(biāo)節(jié)點(diǎn)相等，則說(shuō)明partialPath就是從其出發(fā)到目標(biāo)節(jié)點(diǎn)的路徑，結(jié)果只有這一個(gè)，直接返回
 possiablePaths = partialPath;
 possiablePaths(GLength + 1) = partialWeight;
 return;
elseif length( find( partialPath == destination ) ) ~= 0
 return;
end

%nextNodes中的數(shù)一定大于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); %延長(zhǎng)數(shù)組長(zhǎng)度至GLength+1, 最后一個(gè)元素用于存放該路徑的總路阻
  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的值去掉，因?yàn)橄乱粋€(gè)節(jié)點(diǎn)可能已經(jīng)遍歷過(guò)或者它就是目標(biāo)節(jié)點(diǎn)

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

%輸入桐鄉(xiāng)到富陽(yáng)的高速公路網(wǎng)絡(luò)圖的邊權(quán)矩陣
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;];
%調(diào)用搜索圖中任意兩點(diǎn)間所有路徑的M文件
findPath(a, 1, 7, 0)
輸出結(jié)果：
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