在圖中搜索兩點(diǎn)間的所有路徑matlab編程(共4頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上的 在圖中搜索兩點(diǎn)間所有路徑的M文件function possiablePaths = findPath(Graph, partialPath, destination, partialWeight)% findPath按深度優(yōu)先搜索所有可能的從partialPath出發(fā)到destination的路徑，這些路徑中不包含環(huán)路% Graph: 路網(wǎng)圖，非無窮或0表示兩節(jié)點(diǎn)之間直接連通，矩陣值就為路網(wǎng)權(quán)值% partialPath: 出發(fā)的路徑，如果partialPath就一個數(shù)，表示這個就是起始點(diǎn)% destination: 目標(biāo)節(jié)點(diǎn)% partialWeight: pa

2、rtialPath的權(quán)值，當(dāng)partialPath為一個數(shù)時，partialWeight為0pathLength = length(partialPath);lastNode = partialPath(pathLength); %得到最后一個節(jié)點(diǎn)nextNodes = find(0<Graph(lastNode,:) & Graph(lastNode,:)<inf); %根據(jù)Graph圖得到最后一個節(jié)點(diǎn)的下一個節(jié)點(diǎn)GLength = length(Graph);possiablePaths = ;if lastNode = destination % 如果lastNode

3、與目標(biāo)節(jié)點(diǎn)相等，則說明partialPath就是從其出發(fā)到目標(biāo)節(jié)點(diǎn)的路徑，結(jié)果只有這一個，直接返回 possiablePaths = partialPath; possiablePaths(GLength + 1) = partialWeight; return;elseif length( find( partialPath = destination ) ) = 0 return;end%nextNodes中的數(shù)一定大于0,所以為了讓nextNodes(i)去掉，先將其賦值為0for i=1:length(nextNodes) if destination = nextNodes(i) %

4、輸出路徑 tmpPath = cat(2, partialPath, destination); %串接成一條完整的路徑 tmpPath(GLength + 1) = partialWeight + Graph(lastNode, destination); %延長數(shù)組長度至GLength+1, 最后一個元素用于存放該路徑的總路阻 possiablePaths( length(possiablePaths) + 1 , : ) = tmpPath; nextNodes(i) = 0; elseif length( find( partialPath = nextNodes(i) ) ) = 0

5、 nextNodes(i) = 0; endendnextNodes = nextNodes(nextNodes = 0); %將nextNodes中為0的值去掉，因?yàn)橄乱粋€節(jié)點(diǎn)可能已經(jīng)遍歷過或者它就是目標(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, pos

6、siablePaths, tmpPsbPaths);end%輸入桐鄉(xiā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、 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 1