簡(jiǎn)介一份圍繞Dijkstra算法求最短路徑的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告面向需要完成同類課設(shè)任務(wù)的高校學(xué)生及希望深入理解單源最短路徑實(shí)現(xiàn)的算法初學(xué)者。內(nèi)容以中南大學(xué)課程設(shè)計(jì)為框架覆蓋問(wèn)題分析與任務(wù)定義、數(shù)據(jù)結(jié)構(gòu)選擇與概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)與編碼、上機(jī)調(diào)試四大環(huán)節(jié)詳細(xì)展示了帶權(quán)有向圖的存儲(chǔ)建立、點(diǎn)結(jié)構(gòu)體定義、鄰接矩陣顯示、遞歸函數(shù)應(yīng)用及最終最短路徑輸出的完整過(guò)程。報(bào)告同時(shí)給出測(cè)試用例、調(diào)試中的錯(cuò)誤處理記錄及算法時(shí)間與空間性能分析并附有測(cè)試結(jié)果與學(xué)習(xí)心得體會(huì)。資源包內(nèi)共1個(gè)doc文檔大小182KB目錄層次清晰便于直接參考章節(jié)撰寫課程設(shè)計(jì)報(bào)告。這份資源目前已有321人學(xué)習(xí)或下載具有較好的課程設(shè)計(jì)借鑒價(jià)值。1. 為什么課程設(shè)計(jì)躲不開(kāi)Dijkstra從導(dǎo)航到圖論的一步之遙你打開(kāi)地圖搜“從圖書館到東門取快遞”導(dǎo)航給出的不是直線距離而是一條包含轉(zhuǎn)彎、紅綠燈和路段長(zhǎng)度的綜合路徑。換成數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)里那道“Dijkstra算法求最短路徑”本質(zhì)是把交通網(wǎng)絡(luò)抽象成一張帶權(quán)圖節(jié)點(diǎn)是路口邊是路段權(quán)重是長(zhǎng)度或通行代價(jià)然后從某個(gè)起點(diǎn)出發(fā)計(jì)算到其余所有節(jié)點(diǎn)的最短路徑長(zhǎng)度和經(jīng)過(guò)哪些節(jié)點(diǎn)。這個(gè)場(chǎng)景覆蓋了絕大多數(shù)課設(shè)題目校園導(dǎo)航、物流配送、網(wǎng)絡(luò)拓?fù)渖踔劣螒虻貓D尋路都落在這套模型上。課程設(shè)計(jì)報(bào)告要求的不只是“把代碼跑出結(jié)果”還要寫清楚存儲(chǔ)結(jié)構(gòu)為什么這樣選、為什么每次選中的點(diǎn)是全局最優(yōu)、負(fù)權(quán)邊為什么處理不了。這些問(wèn)題在原理上稍繞卻是答辯老師最愛(ài)追問(wèn)的點(diǎn)。這篇博文按課設(shè)交付順序來(lái)講先建立圖模型和算法邏輯再給一份能直接改寫的C代碼然后是測(cè)例設(shè)計(jì)、常見(jiàn)坑和報(bào)告結(jié)構(gòu)最后用一個(gè)打表驗(yàn)證技巧讓代碼的每一步都能當(dāng)面講清楚。適合正在做數(shù)據(jù)結(jié)構(gòu)課設(shè)、復(fù)習(xí)考研數(shù)據(jù)結(jié)構(gòu)或工作中需要快速撿回最短路徑算法的讀者。2. 先理解Dijkstra的貪心邏輯存圖方式、松弛操作與負(fù)權(quán)邊的坑2.1 用鄰接矩陣還是鄰接表課設(shè)最常見(jiàn)的兩種存圖方案Dijkstra處理的是有權(quán)圖G(V, E)V是頂點(diǎn)集合E是邊集合。存儲(chǔ)方式?jīng)Q定了后續(xù)代碼結(jié)構(gòu)也直接決定了能處理的數(shù)據(jù)規(guī)模。課設(shè)里節(jié)點(diǎn)少則幾十、多則上萬(wàn)兩種方案各有適用場(chǎng)景。存圖方式空間復(fù)雜度邊查詢適用場(chǎng)景鄰接矩陣O(V2)O(1)直接訪問(wèn)g[u][v]節(jié)點(diǎn)數(shù)≤1000稠密圖代碼直觀鄰接表vector存pairO(VE)O(度數(shù))遍歷鄰居節(jié)點(diǎn)數(shù)大、稀疏圖配優(yōu)先隊(duì)列鏈?zhǔn)角跋蛐荗(VE)O(度數(shù))數(shù)組模擬鏈表競(jìng)賽常用課設(shè)也可選我的建議是第一版用鄰接矩陣跑通邏輯第二版改成鄰接表加優(yōu)先隊(duì)列報(bào)告里正好能寫兩種實(shí)現(xiàn)的復(fù)雜度對(duì)比回答“為什么做優(yōu)化”就有具體數(shù)據(jù)支撐。鄰接表推薦直接用STL的vector不推薦手寫鏈表指針管理在Delete邊或析構(gòu)時(shí)容易漏內(nèi)存對(duì)課設(shè)來(lái)說(shuō)沒(méi)有額外收益。2.2 松弛操作為什么“當(dāng)前最小距離”可以確定為最終距離算法核心可以拆成兩個(gè)動(dòng)作選擇一個(gè)當(dāng)前dist最小的未訪問(wèn)頂點(diǎn)u然后遍歷u的所有出邊嘗試更新鄰居v的距離更新條件是dist[u] w(u, v) dist[v] 時(shí)把dist[v]改成dist[u] w(u, v)同時(shí)記錄v的前驅(qū)為u?！氨闅v出邊更新鄰居”這個(gè)動(dòng)作在教材里叫松弛對(duì)應(yīng)英文relaxation。選擇u這一步用的是貪心策略可行性建立在“所有邊權(quán)非負(fù)”之上。因?yàn)檫厵?quán)非負(fù)從起點(diǎn)到u的任何后續(xù)路徑都必然先繞到某個(gè)未訪問(wèn)節(jié)點(diǎn)再折回u這條繞路路徑的長(zhǎng)度不會(huì)小于當(dāng)前dist[u]。所以u(píng)一旦被選中dist[u]就已經(jīng)是最終答案之后不再需要修改。提示如果圖中存在負(fù)權(quán)邊上面這套邏輯立刻失效。負(fù)權(quán)邊可能讓已經(jīng)確定最短路徑的節(jié)點(diǎn)通過(guò)繞路得到更小值如果存在負(fù)權(quán)環(huán)最短路理論上沒(méi)有最小值。遇到負(fù)權(quán)圖要換成Bellman-Ford或SPFA。這里還有一個(gè)常見(jiàn)誤用有的教材把“每次選最小dist”實(shí)現(xiàn)成兩層循環(huán)內(nèi)層掃描所有未訪問(wèn)節(jié)點(diǎn)這沒(méi)有問(wèn)題但如果你提前寫了visited標(biāo)記卻又在dist更新后沒(méi)有跳過(guò)舊狀態(tài)就會(huì)重復(fù)處理同一節(jié)點(diǎn)。堆優(yōu)化版本里這個(gè)問(wèn)題的標(biāo)準(zhǔn)解法是彈出時(shí)檢查d是否大于dist[u]大于則丟棄這一行代碼在后續(xù)實(shí)現(xiàn)里很重要。2.3 一維pre數(shù)組與二維path數(shù)組路徑還原的不同層次很多教材在講完dist數(shù)組后會(huì)用一維pre數(shù)組記錄每個(gè)頂點(diǎn)在最短路徑上的前驅(qū)。輸出從起點(diǎn)s到某終點(diǎn)t的路徑時(shí)從t往前回溯直到s再反轉(zhuǎn)順序就行。這個(gè)方案適合單源單終點(diǎn)的輸出。如果題目要求“輸出從任意起點(diǎn)到任意終點(diǎn)的所有最短路徑”一維pre就不夠用了。常見(jiàn)做法是維護(hù)一個(gè)二維數(shù)組path每運(yùn)行一次Dijkstra就填充一行path[i][v]表示從i到v的前驅(qū)節(jié)點(diǎn)最終能還原任意點(diǎn)對(duì)路徑。檢索里常見(jiàn)的說(shuō)法“所有n-1條最短路徑可以用二維數(shù)組path”指的就是這個(gè)。需要注意的是不要用一次Dijkstra得到的pre去還原任意點(diǎn)對(duì)路徑根本不會(huì)經(jīng)過(guò)起點(diǎn)這是課設(shè)報(bào)告里最容易寫錯(cuò)的部分。3. 用C實(shí)現(xiàn)Dijkstra鄰接表優(yōu)先隊(duì)列的完整可運(yùn)行代碼3.1 鄰接表里的pair怎么設(shè)計(jì)鄰接表g[u]保存u的所有出邊每個(gè)出邊用pair表示。C標(biāo)準(zhǔn)庫(kù)的pair默認(rèn)按first升序排序所以把邊的權(quán)重放first、鄰居節(jié)點(diǎn)號(hào)放second優(yōu)先隊(duì)列排序時(shí)就無(wú)需自定義比較函數(shù)。這個(gè)細(xì)節(jié)能省不少代碼也能避免寫錯(cuò)仿函數(shù)。3.2 核心實(shí)現(xiàn)與一個(gè)可直接運(yùn)行的最小示例下面這段代碼以無(wú)向帶權(quán)圖為例輸入第一行是n m表示節(jié)點(diǎn)數(shù)和邊數(shù)接下來(lái)m行是u v w表示一條邊及權(quán)重最后輸入起點(diǎn)s。輸出起點(diǎn)到每個(gè)節(jié)點(diǎn)的最短距離與完整路徑節(jié)點(diǎn)編號(hào)從0開(kāi)始。#include bits/stdc.h using namespace std; const int N 105; const int INF 0x3f3f3f3f; // 約10.6億兩個(gè)INF相加不超int范圍 int n, m, s; vectorpairint, int g[N]; // first權(quán)重second鄰居節(jié)點(diǎn)號(hào) int dist[N], pre[N]; // pre[v]v在最短路徑上的前驅(qū) void dijkstra(int s) { // 0x3f按字節(jié)填充dist每個(gè)元素都等于INF memset(dist, 0x3f, sizeof(dist)); memset(pre, -1, sizeof(pre)); // 小頂堆pair排序時(shí)先比較權(quán)值再比較節(jié)點(diǎn)號(hào) priority_queuepairint, int, vectorpairint, int , greaterpairint, int pq; dist[s] 0; pq.push(make_pair(0, s)); // 起點(diǎn)入堆 while (!pq.empty()) { int d pq.top().first; // 當(dāng)前取出的距離 int u pq.top().second; // 當(dāng)前取出的節(jié)點(diǎn) pq.pop(); // 堆里殘留的舊狀態(tài)直接丟棄 if (d dist[u]) continue; // 遍歷u的所有出邊執(zhí)行松弛 for (int i 0; i (int)g[u].size(); i) { int w g[u][i].first; // 這條邊的權(quán)重 int v g[u][i].second; // 鄰居節(jié)點(diǎn) if (dist[u] w dist[v]) { dist[v] dist[u] w; pre[v] u; // 記錄前驅(qū) pq.push(make_pair(dist[v], v)); // 新?tīng)顟B(tài)入堆 } } } } void printPath(int s, int t) { if (dist[t] INF) { cout no path from s to t endl; return; } vectorint path; for (int v t; v ! -1; v pre[v]) { path.push_back(v); } reverse(path.begin(), path.end()); for (int i 0; i (int)path.size(); i) { if (i) cout - ; cout path[i]; } cout endl; } int main() { cin n m; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back(make_pair(w, v)); g[v].push_back(make_pair(w, u)); // 無(wú)向圖加雙向邊 } cin s; dijkstra(s); for (int i 0; i n; i) { cout dist[ i ] dist[i] , path: ; printPath(s, i); } return 0; }代碼邏輯可以分四步理解初始化階段把所有距離置為INF、前驅(qū)置為-1然后把起點(diǎn)距離置0并壓入堆循環(huán)階段不斷彈出距離最小的節(jié)點(diǎn)如果堆里的距離大于dist中記錄的值說(shuō)明這條狀態(tài)已經(jīng)過(guò)時(shí)直接跳過(guò)松弛階段遍歷當(dāng)前節(jié)點(diǎn)的所有出邊嘗試把鄰居v的距離縮小成功后記錄前驅(qū)并壓入新?tīng)顟B(tài)路徑還原階段從終點(diǎn)沿pre數(shù)組回溯到起點(diǎn)再反轉(zhuǎn)輸出。參數(shù)作用注意事項(xiàng)g[N]鄰接表元素為(w, v)順序?qū)懛磿?huì)導(dǎo)致松弛讀取錯(cuò)誤dist[N]當(dāng)前最短距離算法結(jié)束時(shí)是最終距離pre[N]前驅(qū)數(shù)組-1表示起點(diǎn)或無(wú)前驅(qū)pq優(yōu)先隊(duì)列保證每輪拿到最小距離候選最大的坑就在pair順序上。C的pair默認(rèn)排序先看first所以g[u]里存(w, v)時(shí)first是權(quán)重一旦寫成(v, w)優(yōu)先隊(duì)列排序結(jié)果完全錯(cuò)誤而且g[u][i].first被當(dāng)成節(jié)點(diǎn)號(hào)運(yùn)行時(shí)不報(bào)錯(cuò)但結(jié)果全錯(cuò)。如果覺(jué)得pair可讀性差換成自定義Edge結(jié)構(gòu)體后需要在priority_queue里重載比較運(yùn)算符工作量其實(shí)更大。3.3 路徑還原的邊界細(xì)節(jié)pre[v]的更新時(shí)機(jī)是“松弛真正發(fā)生”的時(shí)候也就是dist[u] w dist[v]成立時(shí)才把pre[v]設(shè)為u。用小于號(hào)而不是小于等于號(hào)有一個(gè)效果當(dāng)兩條路徑距離相同時(shí)保留原來(lái)的前驅(qū)不產(chǎn)生不必要的變化。如果題目要求輸出“所有最短路徑中任意一條”這個(gè)行為沒(méi)有問(wèn)題如果要求保留所有等價(jià)路徑需要額外維護(hù)每個(gè)節(jié)點(diǎn)的前驅(qū)集合。printPath從終點(diǎn)t開(kāi)始回溯for循環(huán)里的v pre[v]讓v不斷向前移動(dòng)直到pre值為-1也就是起點(diǎn)。這里不用額外記錄起點(diǎn)是誰(shuí)回溯到pre[v]-1時(shí)自然停在起點(diǎn)。需要注意如果圖不連通dist[t]仍為INF要單獨(dú)判斷否則回溯會(huì)走進(jìn)死循環(huán)。3.4 復(fù)雜度分析與課設(shè)選型建議樸素版的復(fù)雜度是O(V2)來(lái)源是每輪都要在未訪問(wèn)節(jié)點(diǎn)中掃描一遍找最小值堆優(yōu)化版把找最小值這一步降為O(logV)每條邊最多被松弛一次總復(fù)雜度O((VE)logV)。稠密圖里E接近V2堆優(yōu)化優(yōu)勢(shì)不明顯稀疏圖里兩者差距非常大節(jié)點(diǎn)數(shù)從一千漲到十萬(wàn)樸素版基本無(wú)法運(yùn)行。課程設(shè)計(jì)如果數(shù)據(jù)范圍小比如城市數(shù)n≤50交樸素版就夠報(bào)告里還能順帶比較“樸素實(shí)現(xiàn)”和“堆優(yōu)化實(shí)現(xiàn)”的時(shí)間差距。如果題目給了大數(shù)據(jù)文件直接上堆優(yōu)化版并且報(bào)告寫明“優(yōu)先隊(duì)列保證每次O(logV)取到最小值因此總開(kāi)銷為O((VE)logV)”。兩種版本的代碼本質(zhì)只有堆操作的區(qū)別核心松弛邏輯完全一致先寫樸素版再改成堆優(yōu)化比一上來(lái)就寫堆更容易排查錯(cuò)誤。4. 把課設(shè)從代碼變成報(bào)告測(cè)例設(shè)計(jì)、排錯(cuò)與答辯要點(diǎn)4.1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告的結(jié)構(gòu)怎么映射一份能拿高分的數(shù)據(jù)結(jié)構(gòu)課設(shè)報(bào)告通常包含需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、測(cè)試分析和總結(jié)。每個(gè)部分和本文代碼的對(duì)應(yīng)關(guān)系大致如下報(bào)告章節(jié)對(duì)應(yīng)內(nèi)容寫作重點(diǎn)需求分析問(wèn)題描述、輸入輸出定義定義節(jié)點(diǎn)、邊、權(quán)重的含義說(shuō)明要輸出什么概要設(shè)計(jì)圖的ADT與存儲(chǔ)結(jié)構(gòu)選擇說(shuō)明為何選鄰接表優(yōu)先隊(duì)列詳細(xì)設(shè)計(jì)函數(shù)接口與核心流程用圖表列出dijkstra、printPath的輸入輸出測(cè)試分析測(cè)試數(shù)據(jù)、運(yùn)行截圖、復(fù)雜度實(shí)測(cè)含邊界測(cè)例和異常輸入總結(jié)算法優(yōu)缺點(diǎn)與改進(jìn)方向可以提Floyd的全源對(duì)比、負(fù)權(quán)圖的限制寫詳細(xì)設(shè)計(jì)時(shí)最忌諱把整段源碼貼上去。報(bào)告正文只保留核心函數(shù)簽名、參數(shù)表格和一段話的設(shè)計(jì)說(shuō)明完整代碼放附錄評(píng)審要看代碼時(shí)再翻附錄。需求分析里把“路徑規(guī)劃”與“最短路徑”聯(lián)系起來(lái)的段落要寫清楚這是課程設(shè)計(jì)的立題所在。4.2 五個(gè)必測(cè)用例重邊、孤立點(diǎn)、零權(quán)邊、大圖、多組數(shù)據(jù)用例輸入要點(diǎn)期望結(jié)果易錯(cuò)點(diǎn)常規(guī)連通圖普通帶權(quán)圖所有dist有值前驅(qū)數(shù)組被上一組數(shù)據(jù)殘留污染重邊0-1出現(xiàn)權(quán)重3和5自動(dòng)取3鄰接表保存兩條邊松弛后只留小的零權(quán)邊0-1權(quán)重0、1-2權(quán)重2dist[2]2判斷用不要用避免零權(quán)環(huán)增加日志孤立點(diǎn)某節(jié)點(diǎn)無(wú)任何邊dist保持INF輸出時(shí)判斷INF不能當(dāng)數(shù)字打印大規(guī)模隨機(jī)圖n10000, m1000001秒內(nèi)出結(jié)果鄰接矩陣會(huì)爆內(nèi)存必須用鄰接表多組數(shù)據(jù)是課設(shè)里容易忽略的。如果題目要求一次運(yùn)行處理多組詢問(wèn)每組都要重新調(diào)用一次dijkstra那init部分的reset就必須包含dist、pre和每個(gè)vector的clear。我自己的習(xí)慣是在dijkstra函數(shù)內(nèi)部完成所有重置外部不依賴上一次運(yùn)行的狀態(tài)這樣每組數(shù)據(jù)獨(dú)立不會(huì)互相污染。提示輸出dist為INF的節(jié)點(diǎn)時(shí)不能直接打印整數(shù)。寫成dist[i] INF ? INF : to_string(dist[i])報(bào)告里能區(qū)分“不可達(dá)”和“距離非常大”也更符合真實(shí)場(chǎng)景。4.3 五個(gè)高頻運(yùn)行異常與排查方向異?，F(xiàn)象可能原因處理方式段錯(cuò)誤節(jié)點(diǎn)號(hào)越界或vector未初始化檢查下標(biāo)從0還是1開(kāi)始數(shù)組開(kāi)N5輸出全為0memset的size寫錯(cuò)檢查sizeof(dist)是否被寫錯(cuò)路徑打印死循環(huán)pre回溯不到起點(diǎn)檢查起點(diǎn)pre未被正確初始化運(yùn)行超時(shí)用了樸素版本且V很大換成優(yōu)先隊(duì)列堆優(yōu)化版數(shù)值異常用INT_MAX參與加法導(dǎo)致溢出改用0x3f3f3f3f或long longINF的選取是這個(gè)實(shí)驗(yàn)里最經(jīng)典的問(wèn)題。INT_MAX加上任意正權(quán)邊會(huì)直接溢出成負(fù)數(shù)導(dǎo)致松弛判斷完全失效。0x3f3f3f3f約等于10.6億兩個(gè)這樣的數(shù)相加約21.2億仍在int范圍內(nèi)不會(huì)溢出。如果權(quán)重上限很大比如達(dá)到1e9且路徑跨越多條邊dist數(shù)組應(yīng)改成long longINF換成長(zhǎng)整型版本的0x3f3f3f3f3f3f3f3f。4.4 答辯高頻對(duì)比BFS、Floyd、SPFA與Dijkstra算法適用場(chǎng)景復(fù)雜度限制BFS無(wú)權(quán)圖O(VE)不能處理帶權(quán)邊Dijkstra非負(fù)權(quán)圖、單源O((VE)logV)無(wú)法處理負(fù)權(quán)邊Floyd任意圖、全源O(V3)小規(guī)模好用負(fù)權(quán)環(huán)不可SPFA/Bellman-Ford負(fù)權(quán)邊無(wú)負(fù)環(huán)最壞O(VE)有負(fù)環(huán)時(shí)不能收斂答辯最常問(wèn)的一句是“為什么不用BFS”。答案很簡(jiǎn)單BFS按層擴(kuò)展只能保證邊數(shù)最少邊數(shù)少不等于權(quán)重總和最小一旦邊帶權(quán)BFS的“第一層先到達(dá)”策略就失效。把這張表放進(jìn)報(bào)告或答辯PPT里基本能應(yīng)對(duì)算法選型類提問(wèn)。5. 打表驗(yàn)證法讓代碼行為在報(bào)告和答辯現(xiàn)場(chǎng)都能被講清楚最后一招是打表驗(yàn)證法這也是我調(diào)試圖算法最常用的手段。Dijkstra跑出正確結(jié)果只是第一步課設(shè)評(píng)審更看重“你能解釋每一步為什么這樣走”。常見(jiàn)做法是在每次彈出節(jié)點(diǎn)u后打印當(dāng)前選中的節(jié)點(diǎn)和整個(gè)dist數(shù)組形成一張過(guò)程表直接放進(jìn)報(bào)告的測(cè)試分析部分。調(diào)試輸出函數(shù)可以這樣寫void debugPrint(int step, int u, int dist[], int n) { cout step step : choose u , dist ; for (int i 0; i n; i) { if (dist[i] INF) cout INF ; else cout dist[i] ; } cout endl; }調(diào)用位置放在if (d dist[u]) continue;之后這樣打印出來(lái)的是每個(gè)節(jié)點(diǎn)第一次被當(dāng)作最小值處理時(shí)的完整狀態(tài)正好對(duì)應(yīng)貪心策略的核心決策點(diǎn)。拿一個(gè)具體例子驗(yàn)證。四個(gè)節(jié)點(diǎn)的圖邊為0-1權(quán)重5、0-2權(quán)重2、1-2權(quán)重1、2-3權(quán)重3起點(diǎn)為0。手推結(jié)果應(yīng)該是dist[0]0, dist[1]3, dist[2]2, dist[3]5路徑0-2-1和0-2-3。程序運(yùn)行日志應(yīng)逐輪對(duì)應(yīng)輪次被選中節(jié)點(diǎn)松弛更新后的dist數(shù)組10dist[1]5, dist[2]222dist[1]3, dist[3]531無(wú)更新43無(wú)更新把這張表復(fù)制進(jìn)課程設(shè)計(jì)的測(cè)試分析部分然后運(yùn)行一次同樣輸入的代碼把控制臺(tái)日志截圖附在旁邊。評(píng)審看到“手推結(jié)果與程序輸出逐行一致”整套報(bào)告的說(shuō)服力比直接貼運(yùn)行結(jié)果高一個(gè)檔次被問(wèn)到“為什么先選2而不是1”時(shí)也能直接回答因?yàn)閐ist[2]更小完全照著日志講就行。這個(gè)打表方法不依賴任何框架五分鐘就能接進(jìn)現(xiàn)有代碼。本文還有配套的精品資源點(diǎn)擊獲取