c++課設(shè)報(bào)告【基于-Dijkstra算法的最短路徑問題求解】[1]

《c++課設(shè)報(bào)告【基于-Dijkstra算法的最短路徑問題求解】[1]》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、課程設(shè)計(jì)任務(wù)書學(xué)院信息科學(xué)與工程專業(yè)通信工程學(xué)生姓名***學(xué)號(hào)*********設(shè)計(jì)題目基于Dijkstra算法的最短路徑問題求解內(nèi)容及要求：進(jìn)行類的設(shè)計(jì)與實(shí)現(xiàn)，解決最短路徑問題。具體要求如下：（1）采用圖的鄰接矩陣或鄰接表實(shí)現(xiàn)最短路徑問題中圖的存儲(chǔ)；（2）采用Dijkstra算法求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑；（3）將上述功能作為類的成員函數(shù)實(shí)現(xiàn)，編寫主函數(shù)測試上述功能。進(jìn)度安排：第17周：分析題目，查閱課題相關(guān)資料，進(jìn)行類設(shè)計(jì)、算法設(shè)計(jì)；第18周：程序的設(shè)計(jì)、調(diào)試與實(shí)現(xiàn)；第19周：程序測試與分析，撰寫課程設(shè)計(jì)報(bào)告，進(jìn)行

2、答辯驗(yàn)收。指導(dǎo)教師（簽字）：年月日學(xué)院院長（簽字）年月日目錄1需求分析-1-2算法基本原理-1-3類設(shè)計(jì)-2-4詳細(xì)設(shè)計(jì)-3-4.1類的接口設(shè)計(jì)-3-4.2類的實(shí)現(xiàn)-5-4.3主函數(shù)設(shè)計(jì)-10-5DOS界面程序運(yùn)行結(jié)果及分析-11-5.1程序運(yùn)行結(jié)果-11-5.2運(yùn)行結(jié)果分析-12-6基于MFC的圖形界面程序開發(fā)-13-6.1基于MFC的圖形界面程序設(shè)計(jì)-13-6.2程序測試-15-6.3MFC程序編寫總結(jié)-17-7參考文獻(xiàn)-17-1需求分析Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家艾茲格·迪科斯徹發(fā)現(xiàn)的。算法解決的是有向圖中最

3、短路徑問題。舉例來說，如果圖中的頂點(diǎn)表示城市，而邊上的權(quán)重表示著城市間開車行經(jīng)的距離。Dijkstra算法可以用來找到兩個(gè)城市之間的最短路徑。Dijkstra算法的輸入包含了一個(gè)有權(quán)重的有向圖G，以及G中的一個(gè)來源頂點(diǎn)S。我們以V表示G中所有頂點(diǎn)的集合。圖中的每一個(gè)邊，都是兩個(gè)頂點(diǎn)所形成的有序元素對(duì)。(u,v)表示從頂點(diǎn)u到v有路徑相連。假設(shè)E為所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:?E?→[0,∞]定義。因此，w(u,v)就是從頂點(diǎn)u到頂點(diǎn)v的非負(fù)花費(fèi)值(cost)。邊的花費(fèi)可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的花費(fèi)

4、值，就是該路徑上所有邊的花費(fèi)值總和。已知有V中有頂點(diǎn)s及t，Dijkstra算法可以找到s到t的最低花費(fèi)路徑(i.e.最短路徑)。這個(gè)算法也可以在一個(gè)圖中，找到從一個(gè)頂點(diǎn)s到任何其他頂點(diǎn)的最短路徑。1．如果將交通網(wǎng)絡(luò)化成帶權(quán)圖，假如用頂點(diǎn)表示城市，邊表示公路段，則由這些頂點(diǎn)和邊組成的圖可表示溝通個(gè)城市的公路圖，邊的權(quán)用以表示兩個(gè)城市之間的距離或者表示走過這段公路所需要的時(shí)間或通過這段路的難易程度等。作為司機(jī)和乘汽車的人，自然會(huì)關(guān)心如下兩個(gè)問題：（1）從甲地到乙地是否有公路？（2）從甲地到乙地有幾條公路，哪條公路最短或花費(fèi)的代價(jià)

5、最??？這就是我們要討論的最短路徑問題。2.迪杰斯特拉提出的一個(gè)求最短路徑的算法。其基本思想是：按路徑長度遞增的順序，逐個(gè)產(chǎn)生各最短路徑。3．首先引進(jìn)輔助向量dist[]，它的每一個(gè)分量dist[i]表示已經(jīng)找到的且從源點(diǎn)到每一個(gè)終點(diǎn)的當(dāng)前最短路徑長度。它的初態(tài)為：如果從到有弧，則dist[i]為弧的權(quán)值；否則dist[i]為∞。其中，長度為dist[j]=min{dist[i]

6、∈V}的路徑是從出發(fā)的長度最短的一條最短路徑，此路徑為（，）。2算法基本原理根據(jù)以上分析，可以得到如下描述的算法：①假設(shè)用帶權(quán)的鄰接矩陣arce[i]

7、[j]來表示帶權(quán)有向圖，arce[i][j]表示弧<，>上的權(quán)值。若<,>不存在，則置arce[i][j]為∞（在計(jì)算機(jī)上可用允許的最大值代替）。S為已找到的從出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從出發(fā)到圖上其余個(gè)頂點(diǎn)（終點(diǎn)）可能達(dá)到的最短路徑長度的初值為：dist[i]=arce[LocateVex(G,)][i]∈S②選擇得dist[j]=min{dist[i]

8、∈V-S}就是當(dāng)前求得的一條從出發(fā)的最短路徑的終點(diǎn)。令S=S∪{j}。③修改從出發(fā)到集合V-S上任一頂點(diǎn)可達(dá)的最短頂點(diǎn)長度。如果dist[j]+

9、arce[j][k]

10、）。當(dāng)算法結(jié)束時(shí)，d[v]中儲(chǔ)存的便是從s到v的最短路徑，或者是無窮大（如果路徑不存在的話）。???Dijstra算法的基礎(chǔ)操作是邊的拓展：如果存在一條從u到v的邊，那么從s到v的最短路徑可以通過將邊(u,v)添加到s到u的尾部來拓展。這條路徑的長度是d[u]+w(u,v)。