09電信實驗班 i09660118 徐振飛
1、實驗名稱
實現書本p194頁所描述的單源最短路徑問題
2、實驗目的
（1）掌握並運用分支限界法基本思想
（2）運用分支限界法實現單源最短路徑問題
（3）區分分支限界演算法與回溯演算法的區別，加深對分支限界法理解
3、實驗內容和原理
（1）實驗原理
解單源最短路徑問題的優先佇列式分支限界法用一極小堆（本次實驗我採用包中的優先佇列類priorityqueue來實現）來儲存活結點表。其優先順序是結點所對應的當前路長。演算法從圖g的源頂點s和空優先佇列開始。
結點s被擴充套件後，它的兒子結點被依次插入堆中。此後，演算法從堆中取出具有最小當前路長的結點作為當前擴充套件結點，並依次檢查與當前擴充套件結點相鄰的所有頂點。如果從當前擴充套件結點i到頂點j有邊可達，且從源出發，途經頂點i再到頂點j的所相應的路徑的長度小於當前最優路徑長度，則將該頂點作為活結點插入到活結點優先佇列中。
這個結點的擴充套件過程一直繼續到活結點優先隊列為空時為止。
（2）實驗內容
測試用例：
4、源程式
import
public class shortestpath
初始化圖
getgraphmatrix();
}public void getgraphmatrix()
"請輸入邊總數：");
scanner scan = new scanner(
int m =
"依次輸入兩個頂點號(1~"+n+")和邊長:例如 1 2 3");
for(int i=0;i
}/***@param 求以第i個節點為起點的單源最短路徑
*/public void shortpath(int i)
列印最短路徑結果
"最短路徑：");
for(int j=1;j<=n;j++)
}public static void main(string args )
}class node implements comparable
public int compareto(node o)
else if(dif==0)
else
}}5、實驗結果
輸出結果分析：測試為上述測試用途，輸出結果：1到2的最短路徑為3,1到3的最短路徑為2,1到4的最短路徑為3,1到5的最短路徑為7,1到6的最短路徑為6。輸出結果正確。
6、實驗心得和體會
通過實驗，了解了分支限界法的基本思想。知道了分支限界演算法與回溯演算法的區別。由於本次實驗利用包下的priorityqueue代替演算法中最小堆，免去了編寫實現最小堆的程式**（但這並不表示我不會編寫最小堆程式，在這次實驗中，最小堆的實現並不是主要部分），所以本次實驗實現的相對順利。
實驗二分支結構程式設計
實驗目的 1 掌握c語言邏輯量的表示方法 以0代表 假 1代表 真 學會正確地使用關係表示式和邏輯表示式。2 掌握用if語句實現選擇結構。3 掌握用switch語句實現多分支選擇結構。4 掌握選擇結構的巢狀。樣例 實驗內容 從鍵盤輸入一年份，判斷年份是否為閏年。說明 注意程式的輸入和輸出分別是什麼。...
4 分支結構程式new
第四章分支結構程式 一 if語句 功能 判斷合法表示式的值，值為非0，執行語句。一 if的三種形式 1.if 的第一種形式 單項條件判斷 if 表示式 語句 解釋 如果表示式為真，則執行語句，否則不執行語句if a b printf d n a printf d n a 2.if的第二種形式 二選一...
實驗四分頁式儲存管理
自動化1203張千偉201203870323 1 實驗目的 1.熟悉分頁式儲存管理 2.掌握最久未使用演算法以及fifo演算法 2 實驗內容 1.實驗 include include include include define bsize 4 物理塊大小 define psize 16 程序大小 ...