數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書黃琪鈞

20XX數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞匯報人：xxx數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞目錄數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞NEXT課程設(shè)計題目:基于最短路徑算法的物流中心選址姓名:黃琪鈞學(xué)號：2022212815班級：2221803指導(dǎo)教師:余小軍2023年11月14日課程設(shè)計報告要求結(jié)構(gòu)要求1、問題分析：題干：題目的要求是讓我們解決物流中心的選址問題，這就需要我們算出每個節(jié)點到其他節(jié)點的最短路徑長度之和，比較選擇各個節(jié)點的最短路徑的權(quán)值和，最小者則是目標(biāo)點。對于算出每個節(jié)點到其他節(jié)點的最短路徑和我們需要使用Floyd算法。算出我們要找的物流中心地址后使用Dijkstra算法去記錄該物流中心到各個節(jié)點的路徑數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞2、總體設(shè)計：首先我們使用鄰接矩陣表示各個節(jié)點及節(jié)點間路徑的權(quán)值，隨后實現(xiàn)出Dijkstra算法和Floyd算法，Dijkstra算法負(fù)責(zé)記錄物流中心到各節(jié)點的最短路徑，F(xiàn)loyd負(fù)責(zé)找出合適的物流中心3、詳細(xì)設(shè)計(1)圖的表示：使用鄰接矩陣表示圖，使用二維數(shù)組來表示鄰接矩陣。vex：頂點表，使用vector<int>類型存儲圖的頂點信息arc：鄰接矩陣，使用vector<vector<int>>類型表示圖的邊或弧的關(guān)系，其中arc[i][j]表示頂點i到頂點j的邊或弧的信息。vexnum：圖中節(jié)點的個數(shù)。arcnum：圖中邊或弧的個數(shù)(2)Floyd算法的實現(xiàn)：首先，我們獲取圖中頂點的數(shù)量n數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞然后，我們將距離矩陣dist初始化為與鄰接矩陣相同的值這里使用dist=graph來實現(xiàn)接下來，通過三層循環(huán)來計算所有點對之間的最短路徑外層循環(huán)變量k表示中間節(jié)點的索引，中間節(jié)點可以是任意節(jié)點中間節(jié)點的選擇是逐步增加的，即從0開始依次到n-1在第二層和第三層循環(huán)中，我們用i和j分別表示起始節(jié)點和目標(biāo)節(jié)點的索引對于每一對節(jié)點(i,j)，我們檢查經(jīng)過中間節(jié)點k是否可以獲得更短的路徑具體而言，如果從節(jié)點i到節(jié)點k和從節(jié)點k到節(jié)點j的距離都不是無窮大(即存在路徑)，并且將這兩段路徑相加的結(jié)果小于當(dāng)前記錄的距離dist[i][j]，則更新dist[i][j]為新的路徑距離通過不斷更新dist矩陣中的距離值，最終得到了圖中任意兩個節(jié)點之間的最短路徑距離數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞(3)Dijkstra算法的實現(xiàn)：初始化距離矩陣dist和路徑矩陣path，將所有節(jié)點之間的距離初始化為無窮大，將路徑矩陣的初始值設(shè)置為-1(表示無路徑)將源節(jié)點到自身的距離設(shè)置為0創(chuàng)建一個優(yōu)先隊列pq，用于按節(jié)點到源節(jié)點的距離進(jìn)行排序每個優(yōu)先隊列元素是一個pair，其中第一個元素是節(jié)點到源節(jié)點的距離，第二個元素是一個pair，包含節(jié)點本身和其前驅(qū)節(jié)點將源節(jié)點和其到源節(jié)點的距離加入優(yōu)先隊列當(dāng)優(yōu)先隊列不為空時，循環(huán)執(zhí)行以下步驟：取出優(yōu)先隊列中的隊首節(jié)點u和其前驅(qū)節(jié)點prev遍歷節(jié)點u的所有鄰居節(jié)點v數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞如果節(jié)點u能夠到達(dá)節(jié)點v，并且通過節(jié)點u到達(dá)節(jié)點v的距離小于直接到達(dá)節(jié)點v的距離，則更新源節(jié)點到節(jié)點v的最短距離和路徑。同時，將節(jié)點v的前驅(qū)節(jié)點設(shè)置為u，并將節(jié)點v及其到源節(jié)點的距離加入優(yōu)先隊列。循環(huán)結(jié)束后，dist矩陣中存儲的就是源節(jié)點到圖中所有其他節(jié)點的最短距離，path矩陣中存儲的是最短路徑的前驅(qū)節(jié)點(4)打印路徑函數(shù)：首先創(chuàng)建一個空棧s用于存儲路徑上的節(jié)點從目標(biāo)節(jié)點dest開始，通過路徑矩陣反向回溯到源節(jié)點src。具體的回溯邏輯是：當(dāng)前節(jié)點入棧，然后將當(dāng)前節(jié)點更新為路徑矩陣中對應(yīng)位置的節(jié)點，直到回溯到源節(jié)點為止如果回溯到源節(jié)點后仍未找到路徑(即當(dāng)前節(jié)點為-1)，則輸出"未找到路徑"的提示信息數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞將源節(jié)點src也入棧，此時棧中就存儲了完整的源節(jié)點到目標(biāo)節(jié)點的路徑最后依次從棧中取出節(jié)點，并輸出其值，即得到了從源節(jié)點到目標(biāo)節(jié)點的具體路徑4、個性功能介紹將題目所給的示例換成圖(1)初始化函數(shù)將圖中邊的數(shù)量設(shè)置為10，頂點的個數(shù)設(shè)置為4設(shè)置圖的頂點信息，頂點分別為1,2,3,4設(shè)置圖的鄰接矩陣，其中arc[i][j]表示頂點i到頂點j的邊或弧的權(quán)重。在這里，使用了一個二維數(shù)組來表示鄰接矩陣，具體的值包括了頂點之間的連接關(guān)系和權(quán)重信息voidInit_Graph(Graph&GRAPH)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞{GRAPH.arcnum=10GRAPH.vexnum=4GRAPH.vex={1,2,3,4}GRAPH.arc={{0,1,2,3},{2,0,7,INF},{5,6,0,2},{1,INF,4,0}}}5、實現(xiàn)部分(1)圖的表示typedefstructGraph數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞{vector<int>vex;//頂點表vector<vector<int>>arc;//領(lǐng)接矩陣intvexnum;//節(jié)點個數(shù)intarcnum;//邊的個數(shù)}Graph(2)Floyd算法的實現(xiàn)voidFloyd(vector<vector<int>>&graph,vector<vector<int>>&dist){數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞intn=graph.size()//初始化距離矩陣dist=graph//計算所有點對之間的最短路徑for(intk=0;k<n;++k){for(inti=0;i<n;++i){for(intj=0;j<n;++j){if(dist[i][k]<INF&&dist[k][j]<INF&&dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j]數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞NEXT}(3)Dijkstra算法的實現(xiàn)voidDijkstra(vector<vector<int>>&graph,intsrc,vector<vector<int>>&dist,vector<vector<int>>&path){intn=graph.size()dist.resize(n,vector<int>(n,INF));//初始化距離矩陣，將所有節(jié)點之間的距離初始化為無窮大path.resize(n,vector<int>(n,-1));//初始化路徑矩陣，-1表示沒有路徑dist[src][src]=0;//設(shè)置源節(jié)點到自身的距離為0priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計任務(wù)書-2022212815-黃琪鈞//創(chuàng)建優(yōu)先隊列pq，用于按節(jié)點到源節(jié)點的距離進(jìn)行排序pq.push(make_pair(dist[src][src],make_pair(src,src)));//將源節(jié)點和其到源節(jié)點的距離加入優(yōu)先隊列while(!pq.empty()){//當(dāng)優(yōu)先隊列不為空時循環(huán)intu=pq.top().second.first;//取出隊首節(jié)點uintprev=pq.top().second.second;//取出節(jié)點u的前驅(qū)節(jié)點prevpq.pop();//彈出隊首節(jié)點for(intv=0;v<n;++v){//遍歷節(jié)點u的所有鄰居節(jié)點vif(graph[u]