資源描述：
《單源點最短路徑問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、《算法設(shè)計與分析》實驗報告實驗名稱：單源點最短路徑問題任課教師：專業(yè)：學(xué)號：姓名：完成日期：2013.12.20成績：________________一、實驗?zāi)康模赫页鲆粋€有向圖中起點到其余各點之間的最短路，并得出最短路的大小二、實驗內(nèi)容：單源點最短路徑問題，即已知一個n結(jié)點有向圖G＝（V,E）和邊的權(quán)函數(shù)c（e），求由某指定結(jié)點V0到其他各個結(jié)點的最短路徑，這里還假定所有的權(quán)都是正的，本實驗要求輸出最短路徑值以及最短路徑。三、程序設(shè)計說明：(算法設(shè)計思路)建立一個集合S，開始時初始化為空，在圖中，將第一個點的最小距離估計值定義為
2、0，其他的定義為最大值，先將第一個點移到S中，然后更新與第一點相連的各點的距離估計值。然后再找最小距離估計值的點，移到S中，再重復(fù)更新，如此循環(huán),就能得到從起點到其他各點的最短路大小。新建一個一維數(shù)組，數(shù)組中存放著到達(dá)每個點的前一個點，從后往前搜索，就可以得到到各點的路徑。四、程序代碼（經(jīng)調(diào)試正確的源程序）usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespacedijkstra3{//再次來嘗試，前兩次失敗是因為整
3、體思路不明晰和數(shù)組溢出，這次再重新嘗試一下//classProgram{staticintN=6;staticintMAX=1000;staticint[,]w=newint[7,7]{{0,0,0,0,0,0,0},{0,0,1,12,MAX,MAX,MAX},{0,MAX,0,9,3,MAX,MAX},{0,MAX,MAX,0,MAX,5,MAX},{0,MAX,MAX,4,0,13,15},{0,MAX,MAX,MAX,MAX,0,4},{0,MAX,MAX,MAX,MAX,MAX,0}};staticint[]d=newi
4、nt[N+1];staticint[]S=newint[7]{0,0,0,0,0,0,0};staticint[]a=newint[7];staticvoidMain(string[]args){inti;Dijkstra(1);Console.Write("從起點到其余各的最短路分別為點：");for(i=1;i<=N;i++){Console.Write(d[i]+"");}Console.WriteLine();for(inta=0;a<=N;a++){Console.Write("起點到{0}點的路徑",a);if(a>=
5、1&&a<=N){Console.Write(a);if(a>1){Console.Write("《");}output(a);}Console.WriteLine();}Console.ReadKey();}staticvoidoutput(intx){if(a[x]<=N){intf=a[x];Console.Write(f);if(f>1)Console.Write("《");output(f);}}staticintextract_min(){intu=0;inti;for(i=1;i<=N;i++){if(S[i]==0
6、&&d[i]d[u]+w[u,v]){d[v]=d[u]+w[u,v];a[v]=u;}}}}}}}五．程序運行結(jié)果（測試數(shù)據(jù)和運行結(jié)果）六、算法復(fù)雜性分析（對所編
7、寫程序的時間復(fù)雜性和空間復(fù)雜性的分析）T(n)=θ()七、實驗中遇到的問題及解決方法八、實驗總結(jié)注：實驗報告填寫時，注意輸入信息的字體格式（宋體、五號），如果用復(fù)制應(yīng)采用選擇性粘貼的“無格式文本”方法完成；“程序運行結(jié)果”請以屏幕拷貝的方式將運行結(jié)果的截圖復(fù)制在報告中。
