分支限界法實(shí)現(xiàn)單源最短路徑問題.doc

《分支限界法實(shí)現(xiàn)單源最短路徑問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、實(shí)驗(yàn)五分支限界法實(shí)現(xiàn)單源最短路徑一實(shí)驗(yàn)題目：分支限界法實(shí)現(xiàn)單源最短路徑問題二實(shí)驗(yàn)要求：區(qū)分分支限界算法與回溯算法的區(qū)別，加深對(duì)分支限界法的理解。三實(shí)驗(yàn)內(nèi)容：解單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法用一極小堆來存儲(chǔ)活結(jié)點(diǎn)表。其優(yōu)先級(jí)是結(jié)點(diǎn)所對(duì)應(yīng)的當(dāng)前路長(zhǎng)。算法從圖G的源頂點(diǎn)s和空優(yōu)先隊(duì)列開始。結(jié)點(diǎn)s被擴(kuò)展后，它的兒子結(jié)點(diǎn)被依次插入堆中。此后，算法從堆中取出具有最小當(dāng)前路長(zhǎng)的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。如果從當(dāng)前擴(kuò)展結(jié)點(diǎn)i到頂點(diǎn)j有邊可達(dá)，且從源出發(fā)，途經(jīng)頂點(diǎn)i再到頂點(diǎn)j的所相應(yīng)的路徑的長(zhǎng)度小于當(dāng)前最優(yōu)路徑長(zhǎng)度，則將該頂點(diǎn)作為活結(jié)點(diǎn)插入到活結(jié)

2、點(diǎn)優(yōu)先隊(duì)列中。這個(gè)結(jié)點(diǎn)的擴(kuò)展過程一直繼續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。四實(shí)驗(yàn)代碼#includeusingnamespacestd;constintsize=100;constintinf=5000;//兩點(diǎn)距離上界constintn=6;//圖頂點(diǎn)個(gè)數(shù)加1intprev[n];//圖的前驅(qū)頂點(diǎn)intdist[]={0,0,5000,5000,5000,5000};//最短距離數(shù)組intc[n][n]={{0,0,0,0,0,0},{0,0,2,3,5000,5000},//圖的鄰接矩陣{0,5000,0,1,2,5000},{0,5000,5000,0

3、,9,2},{0,5000,5000,5000,0,2},{0,5000,5000,5000,5000,0}};constintn=5;//圖頂點(diǎn)個(gè)數(shù)加1intprev[n];//圖的前驅(qū)頂點(diǎn)intdist[]={0,0,5000,5000,5000};intc[][n]={{0,0,0,0,0},{0,0,2,3,5000},{0,5000,0,1,2},{0,5000,5000,0,9},{0,5000,5000,5000,0}};classMinHeapNode{public:inti;//頂點(diǎn)編號(hào)intlength;//當(dāng)前路長(zhǎng)};//循環(huán)隊(duì)列classCirQu

4、eue{private:intfront,rear;MinHeapNodedata[size];public:CirQueue(){front=rear=0;}//元素入隊(duì)操作voidqueryIn(MinHeapNodee){if((rear+1)%size!=front){rear=(rear+1)%size;//隊(duì)尾指針在循環(huán)意義下加1data[rear]=e;//在隊(duì)尾插入元素}}//元素出隊(duì)操作MinHeapNodequeryOut(){if(rear!=front){front=(front+1)%size;//隊(duì)列在循環(huán)意義下加1returndata[fro

5、nt];}}//讀取隊(duì)頭元素，但不出隊(duì)MinHeapNodegetQuery(){if(rear!=front){returndata[(front+1)%size];}}//判斷隊(duì)列是否為空boolempty(){returnfront==rear;}//判斷隊(duì)列是否為滿boolfull(){return(rear+1)%size==front;}};//CirQueue結(jié)束classGraph{public:/***單源最短路徑問題的優(yōu)先隊(duì)列式分支限界法*/voidshortestPath(intv){CirQueueqq;//定義源為初始擴(kuò)展結(jié)點(diǎn)MinHeapNod

6、ee;e.i=v;e.length=0;dist[v]=0;qq.queryIn(e);//搜索問題的解空間while(true){for(intj=1;j=n){break;}MinHeapNodem=qq.getQuery();if((c[m.i][j]

7、(qq.full()){break;}qq.queryIn(mi);//元素入隊(duì)}}//for循環(huán)結(jié)束if(qq.empty()){break;}qq.queryOut();//當(dāng)該結(jié)點(diǎn)的孩子結(jié)點(diǎn)全部入隊(duì)后，刪除該結(jié)點(diǎn)}//while循環(huán)結(jié)束}//方法結(jié)束};//類結(jié)束intmain(){Graphg;g.shortestPath(1);cout<<"最短路徑長(zhǎng)為"<