1、實驗五 分支限界法實現單源最短路徑一 實驗題目：分支限界法實現單源最短路徑問題二 實驗要求：區分分支限界算法與回溯算法的區別，加深對分支限界法的理解。三 實驗內容：解單源最短路徑問題的優先隊列式分支限界法用一極小堆來存儲活結點表。其優先級是結點所對應的當前路長。算法從圖G的源頂點s和空優先隊列開始。結點s被擴展后，它的兒子結點被依次插入堆中。此后，算法從堆中取出具有最小當前路長的結點作為當前擴展結點，并依次檢查與當前擴展結點相鄰的所有頂點。如果從當前擴展結點i到頂點j有邊可達，且從源出發，途經頂點i再到頂點j的所相應的路徑的長度小于當前最優路徑長度，則將該頂點作為活結點插入到活結點優先隊列中。

2、這個結點的擴展過程一直繼續到活結點優先隊列為空時為止。四 實驗代碼#include<iostream>using namespace std;const int size = 100;const int inf = 5000; /兩點距離上界const int n = 6; /圖頂點個數加1int prevn; /圖的前驅頂點int dist = 0,0,5000,5000,5000,5000; /最短距離數組int cnn = 0,0,0,0,0,0,0,0,2,3,5000,5000, /圖的鄰接矩陣 0,5000,0,1,2,5000,0,5000,5000,0,9,2, 0

3、,5000,5000,5000,0,2,0,5000,5000,5000,5000,0;const int n = 5; /圖頂點個數加1int prevn; /圖的前驅頂點int dist = 0,0,5000,5000,5000;int cn = 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;class MinHeapNodepublic : int i; /頂點編號 int length; /當前路長;/循環隊列class CirQueueprivate: int front,rear; Mi

4、nHeapNode datasize;public: CirQueue() front = rear = 0; /元素入隊操作 void queryIn(MinHeapNode e) if(rear +1)%size != front) rear = (rear+1)%size; /隊尾指針在循環意義下加1 datarear = e; /在隊尾插入元素 /元素出隊操作 MinHeapNode queryOut() if(rear != front) front = (front+1)%size; /隊列在循環意義下加1 return datafront; /讀取隊頭元素，但不出隊 MinHea

5、pNode getQuery() if(rear != front) return data(front+1)%size; /判斷隊列是否為空bool empty() return front = rear; /判斷隊列是否為滿bool full() return (rear +1)%size = front; ;/CirQueue結束class Graphpublic: /* * 單源最短路徑問題的優先隊列式分支限界法 */ void shortestPath(int v) CirQueue qq;/定義源為初始擴展結點 MinHeapNode e; e.i = v; e.length =

6、0; distv = 0; qq.queryIn(e); /搜索問題的解空間 while(true) for(int j = 1;j<n;j+)if(j>=n) break; MinHeapNode m = qq.getQuery();if(cm.ij<inf)&&(m.length + cm.ij < distj) /頂點i到頂點j可達，且滿足控制約束 distj = m.length + cm.ij; prevj = m.i; /加入活結點優先隊列 MinHeapNode mi; mi.i = j; mi.length = distj; if(qq.

7、full() break; qq.queryIn(mi); /元素入隊 /for循環結束 if(qq.empty() break; qq.queryOut(); /當該結點的孩子結點全部入隊后，刪除該結點 /while循環結束 /方法結束;/類結束int main() Graph g; g.shortestPath(1); cout<<"最短路徑長為 "<<distn-1<<endl; cout<<"中間路徑為： " for(int i =3;i<n;i+) cout<<previ<<" "