最短路徑流程圖和算法

1、算法的設(shè)計(jì)思想本算法采用分支定界算法實(shí)現(xiàn)。構(gòu)造解空間樹為:第一個(gè)城市為根結(jié)點(diǎn),與第一個(gè)城市相鄰的城市為根節(jié)點(diǎn)的第一層子節(jié)點(diǎn),依此類推;每個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)均是和它相鄰的城市;并且從第一個(gè)根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑上不能出現(xiàn)重復(fù)的城市。本算法將具有最佳路線下界的節(jié)點(diǎn)作為最有希望的節(jié)點(diǎn)來(lái)展開解空間樹,用優(yōu)先隊(duì)列實(shí)現(xiàn)。算法的流程如下:從第一個(gè)城市出發(fā),找出和它相鄰的所有城市,計(jì)算它們的路線下界和費(fèi)用,若路線下界或費(fèi)用不滿足要求,將該節(jié)點(diǎn)代表的子樹剪去,否則將它們保存到優(yōu)先隊(duì)列中,并選擇具有最短路線下界的節(jié)點(diǎn)作為最有希望的節(jié)點(diǎn),并保證路徑上沒有回路。當(dāng)找到一個(gè)可行解時(shí),就和以前的可行解比較,選擇一個(gè)較小的解

2、作為當(dāng)前的較優(yōu)解,當(dāng)優(yōu)先隊(duì)列為空時(shí),當(dāng)前的較優(yōu)解就是最優(yōu)解。算法中首先用Dijkstra算法算出所有點(diǎn)到代表乙城市的點(diǎn)的最短距離。算法采用的下界一個(gè)是關(guān)于路徑長(zhǎng)度的下界,它的值為從甲城市到當(dāng)前城市的路線的長(zhǎng)度與用Dijkstra算法算出的當(dāng)前城市到乙城市的最短路線長(zhǎng)度的和;另一個(gè)是總耗費(fèi)要小于1500。偽代碼算法AlgBB(讀文件m1和m2中的數(shù)據(jù)到矩陣length和cost中Dijkstra(lengthDijkstra(costwhile true dofor i1 to 50 do /選擇和node節(jié)點(diǎn)相鄰的城市節(jié)點(diǎn)if shortestlength>optimal or mincost>1500pruningelseif i=50optimal=min(optimal,tmpopt/選當(dāng)前可行解和最優(yōu)解的較小值做最優(yōu)解elseif looped /如果出現(xiàn)回路pruning /剪枝else將城市i插入到優(yōu)先隊(duì)列中end forwhile true doif 優(yōu)先隊(duì)列為空輸出結(jié)果else取優(yōu)先隊(duì)列中的最小節(jié)點(diǎn)if 這個(gè)最小節(jié)點(diǎn)node的路徑