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