1. 項(xiàng)目概述從理論到實(shí)踐的路徑規(guī)劃在工程計(jì)算、科研仿真乃至算法教學(xué)領(lǐng)域我們常常面臨一個(gè)核心問(wèn)題如何在由節(jié)點(diǎn)和連接構(gòu)成的復(fù)雜網(wǎng)絡(luò)中找到兩點(diǎn)之間成本最低的路徑無(wú)論是交通網(wǎng)絡(luò)中的最短行車路線、通信網(wǎng)絡(luò)中的最優(yōu)數(shù)據(jù)傳輸鏈路還是社交網(wǎng)絡(luò)中的影響力傳播分析其底層邏輯都指向了圖論中的最短路徑問(wèn)題。而Dijkstra算法正是解決非負(fù)權(quán)重圖單源最短路徑問(wèn)題的經(jīng)典與基石。今天我們不談復(fù)雜的數(shù)學(xué)推導(dǎo)而是聚焦于一個(gè)更實(shí)際的問(wèn)題如何將這一精妙的算法思想在MATLAB這一強(qiáng)大的數(shù)值計(jì)算與原型開(kāi)發(fā)環(huán)境中從理論公式轉(zhuǎn)化為一行行清晰、高效、可復(fù)用的代碼我接觸過(guò)不少初學(xué)者他們理解了算法的步驟卻在用MATLAB實(shí)現(xiàn)時(shí)感到無(wú)從下手或者寫(xiě)出的代碼效率低下、可讀性差只能處理教科書(shū)上的簡(jiǎn)單例子一旦面對(duì)稍具規(guī)模的矩陣就束手無(wú)策。這背后的原因往往在于沒(méi)有建立起從“算法偽代碼”到“MATLAB矩陣化思維”的橋梁。本文將分享我多次實(shí)現(xiàn)和優(yōu)化Dijkstra算法的經(jīng)驗(yàn)不僅會(huì)給出可直接運(yùn)行的代碼更會(huì)深入剖析每一步的MATLAB實(shí)現(xiàn)技巧、不同數(shù)據(jù)結(jié)構(gòu)的性能差異以及在實(shí)際應(yīng)用中可能遇到的“坑”和應(yīng)對(duì)策略。無(wú)論你是正在完成課程作業(yè)的學(xué)生還是需要在科研項(xiàng)目中快速驗(yàn)證路徑規(guī)劃方案的研究者這篇文章都將為你提供一個(gè)扎實(shí)的、工業(yè)級(jí)的實(shí)現(xiàn)參考。2. 算法核心思想與MATLAB建模策略在動(dòng)手寫(xiě)代碼之前我們必須吃透Dijkstra算法的核心思想并思考如何用MATLAB的數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)雅地表達(dá)它。算法本質(zhì)是一種貪心策略從源點(diǎn)出發(fā)逐步擴(kuò)展到距離源點(diǎn)最近的未訪問(wèn)節(jié)點(diǎn)并以此為基礎(chǔ)更新其鄰居節(jié)點(diǎn)到源點(diǎn)的最短距離估計(jì)。這個(gè)“距離最近”的選取過(guò)程是算法效率的關(guān)鍵。2.1 算法流程的再梳理與關(guān)鍵變量讓我們拋開(kāi)偽代碼用更工程化的語(yǔ)言描述一下流程初始化設(shè)定一個(gè)集合S包含所有已找到最短路徑的節(jié)點(diǎn)一個(gè)數(shù)組dist記錄從源點(diǎn)到每個(gè)節(jié)點(diǎn)的當(dāng)前最短距離估計(jì)一個(gè)數(shù)組prev記錄到達(dá)每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)用于回溯路徑。初始時(shí)S為空dist中源點(diǎn)距離為0其余為無(wú)窮大Infprev全部為空。循環(huán)選取在未加入S的節(jié)點(diǎn)集合中選出dist值最小的節(jié)點(diǎn)u。此時(shí)可以證明dist[u]就是源點(diǎn)到u的最終最短距離。將u加入S。松弛操作對(duì)于節(jié)點(diǎn)u的每一個(gè)鄰居節(jié)點(diǎn)v檢查如果經(jīng)由u到達(dá)v是否更短即判斷dist[u] weight(u, v) dist[v]是否成立。如果成立則更新dist[v] dist[u] weight(u, v)并記錄prev[v] u。重復(fù)重復(fù)步驟2和3直到所有節(jié)點(diǎn)都加入S或者目標(biāo)節(jié)點(diǎn)已加入S針對(duì)單源單目標(biāo)情況。在MATLAB中我們需要為這些抽象變量找到具體的載體圖Graph通常用鄰接矩陣表示。adjMatrix(i, j)的值表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊的權(quán)重。如果i和j不直接相連則權(quán)重為Inf。對(duì)角線元素通常為0。對(duì)于無(wú)向圖矩陣是對(duì)稱的。鄰接矩陣非常直觀適合稠密圖或節(jié)點(diǎn)數(shù)不是特別大的情況。距離數(shù)組dist一個(gè)一維向量dist(1:n)n為節(jié)點(diǎn)總數(shù)。前驅(qū)數(shù)組prev一個(gè)一維向量prev(1:n)用于存儲(chǔ)路徑。初始化為0或NaN。已訪問(wèn)集合S在MATLAB中我們通常用一個(gè)布爾邏輯向量visited(1:n)來(lái)表示visited(i)true表示節(jié)點(diǎn)i已加入S。注意很多教學(xué)實(shí)現(xiàn)會(huì)用數(shù)組存儲(chǔ)未訪問(wèn)節(jié)點(diǎn)集合并線性查找最小值這在節(jié)點(diǎn)數(shù)多時(shí)效率極低O(n2)。在MATLAB中我們可以利用矩陣運(yùn)算和邏輯索引來(lái)優(yōu)化但更高效的做法是模擬優(yōu)先隊(duì)列的思想。2.2 數(shù)據(jù)結(jié)構(gòu)選型鄰接矩陣 vs. 鄰接表這是實(shí)現(xiàn)前必須做出的關(guān)鍵決策直接影響代碼的效率和內(nèi)存占用。鄰接矩陣優(yōu)點(diǎn)實(shí)現(xiàn)簡(jiǎn)單訪問(wèn)任意兩節(jié)點(diǎn)間權(quán)重是O(1)操作。MATLAB對(duì)矩陣運(yùn)算有深度優(yōu)化某些操作向量化后很快。缺點(diǎn)內(nèi)存占用為O(n2)對(duì)于稀疏圖邊數(shù)遠(yuǎn)小于n2極其浪費(fèi)。在查找節(jié)點(diǎn)鄰居時(shí)需要遍歷整行即使大多數(shù)是Inf。適用場(chǎng)景節(jié)點(diǎn)數(shù)量較少例如幾百個(gè)以內(nèi)或圖非常稠密的教學(xué)、演示及小型仿真。鄰接表優(yōu)點(diǎn)內(nèi)存占用為O(ne)與邊數(shù)e成正比非常適合稀疏圖?？梢钥焖佾@取一個(gè)節(jié)點(diǎn)的所有鄰居。缺點(diǎn)MATLAB原生沒(méi)有專門的圖結(jié)構(gòu)雖然R2015b后引入了graph和digraph對(duì)象需要自己用元胞數(shù)組或結(jié)構(gòu)體數(shù)組實(shí)現(xiàn)代碼稍復(fù)雜。查找特定邊(i,j)的權(quán)重需要遍歷列表效率為O(degree(i))。適用場(chǎng)景節(jié)點(diǎn)數(shù)量大、圖稀疏的實(shí)際問(wèn)題如道路網(wǎng)絡(luò)、社交網(wǎng)絡(luò)。對(duì)于本文為了清晰展示算法與MATLAB基礎(chǔ)語(yǔ)法如矩陣索引、Inf、find函數(shù)的結(jié)合我們將首先采用鄰接矩陣實(shí)現(xiàn)一個(gè)基礎(chǔ)版本。在后續(xù)的優(yōu)化章節(jié)我們會(huì)探討基于鄰接表以及利用MATLAB內(nèi)置圖對(duì)象的更高效實(shí)現(xiàn)。理解基礎(chǔ)矩陣版本是邁向高級(jí)優(yōu)化的必經(jīng)之路。3. 基礎(chǔ)實(shí)現(xiàn)鄰接矩陣與循環(huán)版本我們先實(shí)現(xiàn)一個(gè)最直觀、最貼近算法偽代碼的版本。這個(gè)版本使用完整的嵌套循環(huán)易于理解但效率不是最優(yōu)。我們將通過(guò)它來(lái)鞏固對(duì)算法步驟和MATLAB基本操作的理解。3.1 函數(shù)接口設(shè)計(jì)與初始化一個(gè)好的函數(shù)接口能讓代碼更易用。我們的Dijkstra函數(shù)至少需要輸入鄰接矩陣和源節(jié)點(diǎn)輸出最短距離和前驅(qū)節(jié)點(diǎn)。function [dist, prev] dijkstra_basic(adjMatrix, src) % DIJKSTRA_BASIC 使用鄰接矩陣實(shí)現(xiàn)Dijkstra最短路徑算法基礎(chǔ)循環(huán)版 % 輸入 % adjMatrix - n x n 的鄰接矩陣adjMatrix(i,j)為邊(i-j)的權(quán)值無(wú)邊則為Inf % src - 源節(jié)點(diǎn)編號(hào)標(biāo)量 % 輸出 % dist - 1 x n 向量dist(i)表示從源節(jié)點(diǎn)到節(jié)點(diǎn)i的最短距離 % prev - 1 x n 向量prev(i)表示在最短路徑上節(jié)點(diǎn)i的前驅(qū)節(jié)點(diǎn)。用于路徑回溯。 n size(adjMatrix, 1); % 節(jié)點(diǎn)總數(shù) dist inf(1, n); % 初始化距離為無(wú)窮大 prev zeros(1, n); % 初始化前驅(qū)為0 visited false(1, n); % 標(biāo)記節(jié)點(diǎn)是否已訪問(wèn)即已加入S集合 dist(src) 0; % 源節(jié)點(diǎn)到自身的距離為0這里有幾個(gè)細(xì)節(jié)size(adjMatrix, 1)獲取行數(shù)即節(jié)點(diǎn)數(shù)。我們假設(shè)輸入的鄰接矩陣是方陣。inf(1, n)生成一個(gè)1行n列的全I(xiàn)nf向量。Inf在MATLAB中表示無(wú)窮大是距離初始化的理想選擇。false(1, n)生成一個(gè)邏輯假向量比用zeros(1,n)然后在比較時(shí)轉(zhuǎn)換更高效、更清晰。前驅(qū)prev初始化為0這是一個(gè)約定因?yàn)镸ATLAB索引從1開(kāi)始0可以作為一個(gè)無(wú)效標(biāo)識(shí)。后續(xù)回溯路徑時(shí)遇到0即停止。3.2 主循環(huán)與“最近節(jié)點(diǎn)”選取這是算法的核心循環(huán)。我們需要循環(huán)n次每次從未訪問(wèn)節(jié)點(diǎn)中找出dist最小的那個(gè)。for i 1:n-1 % 循環(huán)n-1次即可因?yàn)樽詈笠淮沃皇Ｒ粋€(gè)節(jié)點(diǎn)無(wú)需比較 % 步驟1在未訪問(wèn)節(jié)點(diǎn)中找到當(dāng)前距離最小的節(jié)點(diǎn)u minDist inf; u -1; % 初始化為無(wú)效節(jié)點(diǎn) for v 1:n if ~visited(v) dist(v) minDist minDist dist(v); u v; end end % 如果所有未訪問(wèn)節(jié)點(diǎn)距離都是Inf說(shuō)明剩余節(jié)點(diǎn)不可達(dá)提前結(jié)束 if u -1 break; end visited(u) true; % 將節(jié)點(diǎn)u標(biāo)記為已訪問(wèn)這個(gè)雙重循環(huán)是效率的瓶頸。外層循環(huán)n次內(nèi)層循環(huán)每次都要遍歷n個(gè)節(jié)點(diǎn)來(lái)尋找最小值因此總時(shí)間復(fù)雜度是O(n2)。對(duì)于小規(guī)模圖n1000尚可接受但對(duì)于大規(guī)模圖這將非常緩慢。3.3 松弛操作與鄰居更新找到當(dāng)前最近節(jié)點(diǎn)u后我們需要檢查它的所有鄰居v看能否通過(guò)u縮短到v的距離。% 步驟2松弛操作更新u的所有鄰居的距離 for v 1:n % 確保v是u的鄰居即邊權(quán)不是Inf且v未被訪問(wèn) if ~visited(v) adjMatrix(u, v) ~ inf alt dist(u) adjMatrix(u, v); if alt dist(v) dist(v) alt; prev(v) u; end end end end end這里的關(guān)鍵點(diǎn)是adjMatrix(u, v) ~ inf用于判斷u和v是否直接相連。在鄰接矩陣中不存在的邊用Inf表示。alt是經(jīng)由u到達(dá)v的候選距離。如果候選距離更短就更新dist(v)和prev(v)。prev(v) u意味著在最短路徑上到達(dá)v之前要先經(jīng)過(guò)u。3.4 路徑回溯函數(shù)算法輸出了dist和prev數(shù)組但用戶通常想要的是具體的節(jié)點(diǎn)序列。我們需要一個(gè)輔助函數(shù)來(lái)根據(jù)prev數(shù)組回溯出從源點(diǎn)到任意目標(biāo)點(diǎn)的路徑。function path reconstructPath(prev, target) % RECONSTRUCTPATH 根據(jù)前驅(qū)數(shù)組prev回溯最短路徑 % 輸入 % prev - dijkstra函數(shù)輸出的前驅(qū)向量 % target - 目標(biāo)節(jié)點(diǎn)編號(hào) % 輸出 % path - 從源點(diǎn)到目標(biāo)點(diǎn)的節(jié)點(diǎn)編號(hào)序列行向量如果不可達(dá)則為空數(shù)組 path []; if prev(target) 0 target ~ src % 假設(shè)src是源點(diǎn)這里需要額外傳入簡(jiǎn)易處理 % 目標(biāo)節(jié)點(diǎn)不可達(dá)前驅(qū)為0且不是源點(diǎn)自身 return; end % 從目標(biāo)點(diǎn)向前回溯 u target; while u ~ 0 % 約定源點(diǎn)的前驅(qū)為0 path [u, path]; % 將當(dāng)前節(jié)點(diǎn)插入路徑頭部 u prev(u); end end實(shí)操心得在回溯路徑時(shí)將節(jié)點(diǎn)插入數(shù)組頭部[u, path]會(huì)導(dǎo)致每次操作都涉及數(shù)組重排當(dāng)路徑很長(zhǎng)時(shí)效率不高。一個(gè)更高效的做法是先從目標(biāo)點(diǎn)回溯到源點(diǎn)將節(jié)點(diǎn)順序存入一個(gè)?；蚍聪驍?shù)組然后再反轉(zhuǎn)?；蛘呖梢灶A(yù)先分配一個(gè)足夠大的數(shù)組從后往前填充。對(duì)于教學(xué)和一般使用當(dāng)前方式足夠清晰。4. 優(yōu)化實(shí)現(xiàn)向量化與優(yōu)先隊(duì)列思想基礎(chǔ)循環(huán)版雖然直觀但其O(n2)的復(fù)雜度限制了應(yīng)用范圍。MATLAB的優(yōu)勢(shì)在于矩陣和向量運(yùn)算。我們可以利用邏輯索引進(jìn)行一定程度的向量化并引入“優(yōu)先隊(duì)列”的思想來(lái)大幅優(yōu)化“尋找未訪問(wèn)節(jié)點(diǎn)中dist最小者”這一步驟。4.1 使用邏輯索引進(jìn)行向量化更新在松弛步驟中我們不再顯式循環(huán)遍歷所有節(jié)點(diǎn)v而是通過(guò)一次邏輯索引操作找到所有u的未訪問(wèn)鄰居并向量化地更新它們的距離。function [dist, prev] dijkstra_vectorized(adjMatrix, src) n size(adjMatrix, 1); dist inf(1, n); prev zeros(1, n); visited false(1, n); dist(src) 0; for i 1:n-1 % 找到未訪問(wèn)節(jié)點(diǎn)中dist最小的節(jié)點(diǎn)u % 利用 ~visited 作為掩碼從dist中篩選出未訪問(wèn)節(jié)點(diǎn)的距離 tempDist dist; tempDist(visited) inf; % 將已訪問(wèn)節(jié)點(diǎn)的距離臨時(shí)設(shè)為Inf避免被選到 [minDist, u] min(tempDist); if isinf(minDist) break; % 所有未訪問(wèn)節(jié)點(diǎn)都不可達(dá) end visited(u) true; % 向量化松弛操作 % 1. 找到u的所有未訪問(wèn)鄰居 neighbors ~visited ~isinf(adjMatrix(u, :)); % 邏輯索引未訪問(wèn)且邊權(quán)有限 % 2. 計(jì)算經(jīng)由u到這些鄰居的候選距離 candidateDist dist(u) adjMatrix(u, neighbors); % 3. 比較并更新 updateMask candidateDist dist(neighbors); if any(updateMask) % 找出需要更新的鄰居在原列表中的位置有點(diǎn)繞 neighborIndices find(neighbors); % 獲取鄰居節(jié)點(diǎn)的實(shí)際索引 indicesToUpdate neighborIndices(updateMask); dist(indicesToUpdate) candidateDist(updateMask); prev(indicesToUpdate) u; end end end優(yōu)化解析選取最小節(jié)點(diǎn)tempDist(visited) inf;這一行是關(guān)鍵。它創(chuàng)建了一個(gè)臨時(shí)副本并將已訪問(wèn)節(jié)點(diǎn)的距離設(shè)為Inf這樣min函數(shù)就會(huì)自動(dòng)忽略它們。這避免了內(nèi)層的for循環(huán)利用MATLAB內(nèi)置的、用C語(yǔ)言優(yōu)化的min函數(shù)速度更快。向量化松弛neighbors ~visited ~isinf(adjMatrix(u, :));生成一個(gè)邏輯向量直接標(biāo)出所有滿足“未訪問(wèn)”且“與u相連”的節(jié)點(diǎn)。candidateDist dist(u) adjMatrix(u, neighbors);一次性計(jì)算出所有候選距離。注意adjMatrix(u, neighbors)利用了邏輯索引只取出u到這些鄰居的權(quán)重。updateMask candidateDist dist(neighbors);生成另一個(gè)邏輯向量標(biāo)記出哪些鄰居需要更新。最后通過(guò)find(neighbors)將邏輯索引轉(zhuǎn)換為線性索引只更新那些需要更新的節(jié)點(diǎn)。這個(gè)版本比基礎(chǔ)循環(huán)版快很多尤其是當(dāng)圖的平均度數(shù)較高時(shí)。但它仍然需要每次循環(huán)都執(zhí)行min(tempDist)這本質(zhì)上是一個(gè)線性掃描復(fù)雜度仍是O(n2)。要突破這個(gè)瓶頸我們需要引入優(yōu)先隊(duì)列。4.2 模擬優(yōu)先隊(duì)列優(yōu)化在標(biāo)準(zhǔn)的算法教材中使用優(yōu)先隊(duì)列如二叉堆可以將算法復(fù)雜度降至O((ne) log n)。MATLAB沒(méi)有內(nèi)置的堆數(shù)據(jù)結(jié)構(gòu)但我們可以用一些技巧來(lái)模擬。一種常見(jiàn)且有效的方法是維護(hù)兩個(gè)并行列表一個(gè)存儲(chǔ)未訪問(wèn)節(jié)點(diǎn)的索引另一個(gè)存儲(chǔ)它們對(duì)應(yīng)的當(dāng)前距離。每次迭代我們從這個(gè)列表中找出距離最小的節(jié)點(diǎn)。在更新鄰居距離后我們同步更新這個(gè)列表中的距離值。雖然查找最小值仍然是O(n)但我們可以通過(guò)保持列表有序或者使用min函數(shù)對(duì)較短的列表進(jìn)行操作來(lái)獲得一定提升。然而最徹底的模擬是實(shí)現(xiàn)一個(gè)最小堆。這里給出一個(gè)使用min函數(shù)但通過(guò)動(dòng)態(tài)維護(hù)“未訪問(wèn)節(jié)點(diǎn)列表”來(lái)減少每次掃描數(shù)據(jù)量的簡(jiǎn)化版function [dist, prev] dijkstra_optimized(adjMatrix, src) n size(adjMatrix, 1); dist inf(1, n); prev zeros(1, n); visited false(1, n); dist(src) 0; % 初始化未訪問(wèn)節(jié)點(diǎn)列表為所有節(jié)點(diǎn) unvisited 1:n; while ~isempty(unvisited) % 在當(dāng)前未訪問(wèn)節(jié)點(diǎn)列表中找到dist最小的節(jié)點(diǎn) [minDist, idxInList] min(dist(unvisited)); u unvisited(idxInList); if isinf(minDist) break; % 剩余節(jié)點(diǎn)均不可達(dá) end visited(u) true; % 從unvisited列表中移除u效率關(guān)鍵點(diǎn) unvisited(idxInList) []; % 找出u的未訪問(wèn)鄰居在unvisited列表中的鄰居 % 獲取u的所有鄰居索引邊權(quán)有限 allNeighbors find(~isinf(adjMatrix(u, :)) (adjMatrix(u, :) 0)); % 通常排除自環(huán)和Inf % 求交集allNeighbors 和 unvisited neighbors allNeighbors(ismember(allNeighbors, unvisited)); for v neighbors alt dist(u) adjMatrix(u, v); if alt dist(v) dist(v) alt; prev(v) u; end end end end注意事項(xiàng)這個(gè)版本中unvisited(idxInList) []這行代碼在MATLAB中效率較低因?yàn)樗枰苿?dòng)數(shù)組元素。當(dāng)節(jié)點(diǎn)數(shù)很大時(shí)這會(huì)成為新的瓶頸。真正的優(yōu)先隊(duì)列實(shí)現(xiàn)需要自定義一個(gè)最小堆類來(lái)支持O(log n)的提取最小值和更新鍵值操作。由于代碼較長(zhǎng)這里不展開(kāi)但其思路是維護(hù)一個(gè)堆堆頂始終是dist最小的未訪問(wèn)節(jié)點(diǎn)。每次松弛更新后如果某個(gè)鄰居的dist變小了就需要將該節(jié)點(diǎn)在堆中的位置上浮decrease-key操作。核心建議對(duì)于大多數(shù)在MATLAB中處理中等規(guī)模圖節(jié)點(diǎn)數(shù)在幾千到一兩萬(wàn)的場(chǎng)景經(jīng)過(guò)邏輯索引優(yōu)化的dijkstra_vectorized版本通常是一個(gè)在實(shí)現(xiàn)復(fù)雜度和運(yùn)行效率之間取得良好平衡的選擇。除非你處理的是超大規(guī)模稀疏圖如全國(guó)路網(wǎng)否則引入復(fù)雜的堆結(jié)構(gòu)帶來(lái)的性能提升可能不如直接使用MATLAB內(nèi)置的圖算法工具箱。5. 使用MATLAB內(nèi)置圖對(duì)象與最短路徑函數(shù)從MATLAB R2015b開(kāi)始官方引入了graph和digraph對(duì)象并提供了豐富的圖算法函數(shù)其中就包括shortestpath和distances函數(shù)它們默認(rèn)使用的就是Dijkstra算法對(duì)于非負(fù)權(quán)重。這是最推薦在生產(chǎn)代碼或科研中使用的方案因?yàn)樗?jīng)過(guò)了高度優(yōu)化穩(wěn)定且功能強(qiáng)大。5.1 創(chuàng)建圖對(duì)象并計(jì)算最短路徑假設(shè)我們有一個(gè)邊的列表包含起點(diǎn)、終點(diǎn)和權(quán)重。% 示例創(chuàng)建一個(gè)小型有向圖 s [1 1 2 3 3 4]; % 起點(diǎn)列表 t [2 3 4 4 5 5]; % 終點(diǎn)列表 w [10 5 2 9 3 4]; % 權(quán)重列表 G digraph(s, t, w); % 創(chuàng)建有向加權(quán)圖 % 如果是無(wú)向圖使用 graph(s, t, w) % 計(jì)算從節(jié)點(diǎn)1到節(jié)點(diǎn)5的最短路徑和距離 [path, d] shortestpath(G, 1, 5); disp([最短路徑, num2str(path)]); disp([最短距離, num2str(d)]); % 計(jì)算從節(jié)點(diǎn)1到所有其他節(jié)點(diǎn)的最短距離 dist_all distances(G, 1); disp(從節(jié)點(diǎn)1到各節(jié)點(diǎn)的距離); disp(dist_all);優(yōu)勢(shì)分析簡(jiǎn)潔高效一兩行代碼解決問(wèn)題無(wú)需自己實(shí)現(xiàn)算法。功能全面shortestpath函數(shù)自動(dòng)處理路徑回溯distances函數(shù)計(jì)算單源或多源最短距離。性能優(yōu)越底層由C/C實(shí)現(xiàn)并針對(duì)稀疏矩陣進(jìn)行了優(yōu)化速度遠(yuǎn)超一般的自寫(xiě)M文件?？梢暬煽梢灾苯佑胮lot(G)繪圖用highlight高亮最短路徑非常適合分析和演示。5.2 處理鄰接矩陣輸入如果你的數(shù)據(jù)已經(jīng)是鄰接矩陣形式可以輕松地轉(zhuǎn)換為圖對(duì)象。% 假設(shè) adjMatrix 是你的 n x n 鄰接矩陣 n size(adjMatrix, 1); [s, t, w] find(adjMatrix); % 找出所有非零非Inf元素的索引和值 % 注意find會(huì)找到所有非零元素包括對(duì)角線。如果對(duì)角線是0需要排除。 nonDiagonal (s ~ t); % 排除自環(huán) s s(nonDiagonal); t t(nonDiagonal); w w(nonDiagonal); % 將Inf權(quán)重轉(zhuǎn)換為邊通常Inf表示無(wú)邊所以不應(yīng)該加入圖。 % 更安全的做法是在創(chuàng)建adjMatrix時(shí)不存在的邊用0表示然后 % [s, t, w] find(adjMatrix); % G digraph(s, t, w); % 或者使用稀疏矩陣直接構(gòu)建G digraph(adjMatrix); 但要求adjMatrix是稀疏矩陣且權(quán)重在非零元素中。 % 推薦做法如果原始數(shù)據(jù)是Inf表示無(wú)邊先將其替換為0 adjMatrixForGraph adjMatrix; adjMatrixForGraph(isinf(adjMatrix)) 0; G digraph(adjMatrixForGraph, omitselfloops); % omitselfloops忽略自環(huán)實(shí)操心得當(dāng)需要頻繁對(duì)同一個(gè)圖進(jìn)行多次最短路徑查詢時(shí)構(gòu)建一次graph對(duì)象并重復(fù)調(diào)用shortestpath是最高效的方式。內(nèi)置函數(shù)還支持指定算法如positive對(duì)應(yīng)Dijkstraunweighted對(duì)應(yīng)BFS等非常靈活。6. 實(shí)戰(zhàn)應(yīng)用與性能對(duì)比測(cè)試?yán)碚撛俸靡残枰獙?shí)踐檢驗(yàn)。我們來(lái)設(shè)計(jì)一個(gè)簡(jiǎn)單的實(shí)驗(yàn)對(duì)比我們實(shí)現(xiàn)的幾個(gè)版本與MATLAB內(nèi)置函數(shù)的性能并展示一個(gè)實(shí)際應(yīng)用場(chǎng)景。6.1 性能對(duì)比實(shí)驗(yàn)我們生成不同規(guī)模的隨機(jī)圖進(jìn)行測(cè)試。% 性能測(cè)試腳本 nodeSizes [50, 100, 200, 500]; % 測(cè)試不同節(jié)點(diǎn)規(guī)模 results cell(length(nodeSizes), 5); % 存儲(chǔ)結(jié)果節(jié)點(diǎn)數(shù)基礎(chǔ)版時(shí)間向量化版時(shí)間優(yōu)化版時(shí)間內(nèi)置函數(shù)時(shí)間 for idx 1:length(nodeSizes) n nodeSizes(idx); fprintf(測(cè)試節(jié)點(diǎn)數(shù) n %d...\n, n); % 生成一個(gè)隨機(jī)稀疏鄰接矩陣密度約10% density 0.1; adj sprand(n, n, density); % 生成稀疏隨機(jī)矩陣0-1之間 adj adj speye(n); % 確保對(duì)角線為1自環(huán)距離為0 adj(adj 0) adj(adj 0) * 10; % 給非零元素一個(gè)權(quán)重1-10 % 將未連接的部分設(shè)為Inf對(duì)于全矩陣操作轉(zhuǎn)為滿矩陣 adjMatrix full(adj); adjMatrix(adjMatrix 0) inf; adjMatrix(1:n1:end) 0; % 對(duì)角線置0 src 1; % 計(jì)時(shí)基礎(chǔ)循環(huán)版 tic; [~, ~] dijkstra_basic(adjMatrix, src); time_basic toc; % 計(jì)時(shí)向量化版 tic; [~, ~] dijkstra_vectorized(adjMatrix, src); time_vec toc; % 計(jì)時(shí)優(yōu)化列表版 tic; [~, ~] dijkstra_optimized(adjMatrix, src); time_opt toc; % 計(jì)時(shí)內(nèi)置函數(shù)需轉(zhuǎn)換為圖對(duì)象 tic; adjForGraph adjMatrix; adjForGraph(isinf(adjForGraph)) 0; G digraph(adjForGraph, omitselfloops); dist_builtin distances(G, src); time_builtin toc; results{idx, 1} n; results{idx, 2} time_basic; results{idx, 3} time_vec; results{idx, 4} time_opt; results{idx, 5} time_builtin; end % 展示結(jié)果 fprintf(\n性能對(duì)比結(jié)果單位秒:\n); fprintf(節(jié)點(diǎn)數(shù)\t基礎(chǔ)循環(huán)\t向量化\t\t優(yōu)化列表\t內(nèi)置函數(shù)\n); fprintf(------------------------------------------------------------\n); for idx 1:size(results, 1) fprintf(%d\t%.4f\t\t%.4f\t\t%.4f\t\t%.4f\n, ... results{idx,1}, results{idx,2}, results{idx,3}, results{idx,4}, results{idx,5}); end預(yù)期結(jié)果分析通常基礎(chǔ)循環(huán)版會(huì)最慢向量化版有明顯提升優(yōu)化列表版在小規(guī)模時(shí)可能不如向量化版因?yàn)榫S護(hù)列表有開(kāi)銷但在大規(guī)模稀疏圖上優(yōu)勢(shì)會(huì)顯現(xiàn)。而內(nèi)置函數(shù)幾乎總是最快的并且優(yōu)勢(shì)隨著規(guī)模增大而急劇擴(kuò)大。這個(gè)實(shí)驗(yàn)?zāi)苤庇^地告訴你在什么場(chǎng)景下該選擇哪種實(shí)現(xiàn)。6.2 應(yīng)用案例校園導(dǎo)航路徑規(guī)劃假設(shè)我們要為一個(gè)校園的若干地點(diǎn)規(guī)劃最短路徑。我們手動(dòng)定義一個(gè)鄰接矩陣表示地點(diǎn)間的步行時(shí)間分鐘。% 定義地點(diǎn)1-圖書(shū)館2-教學(xué)樓A3-教學(xué)樓B4-食堂5-體育館6-宿舍 n 6; adjMatrix inf(n); % 初始化為無(wú)窮大 adjMatrix(1,2)5; adjMatrix(1,3)8; adjMatrix(2,1)5; adjMatrix(2,3)2; adjMatrix(2,4)10; adjMatrix(3,1)8; adjMatrix(3,2)2; adjMatrix(3,5)4; adjMatrix(4,2)10; adjMatrix(4,5)3; adjMatrix(4,6)12; adjMatrix(5,3)4; adjMatrix(5,4)3; adjMatrix(5,6)6; adjMatrix(6,4)12; adjMatrix(6,5)6; % 無(wú)向圖所以矩陣本應(yīng)是對(duì)稱的上面已經(jīng)手動(dòng)對(duì)稱賦值了。 adjMatrix(1:n1:end) 0; % 對(duì)角線置0 src 6; % 從宿舍出發(fā) target 1; % 去圖書(shū)館 % 使用我們的向量化實(shí)現(xiàn) [dist, prev] dijkstra_vectorized(adjMatrix, src); path reconstructPath(prev, target); % 需要稍作修改將src作為參數(shù)傳入 fprintf(從宿舍到圖書(shū)館的最短步行時(shí)間%.1f 分鐘\n, dist(target)); fprintf(路徑); for i 1:length(path) fprintf(%d , path(i)); if i length(path) fprintf(- ); end end fprintf(\n); % 使用內(nèi)置函數(shù)驗(yàn)證 G graph(adjMatrix, upper, omitselfloops); % upper因?yàn)槲覀兊木仃囀菍?duì)稱的 [path_builtin, dist_builtin] shortestpath(G, src, target); fprintf(\n內(nèi)置函數(shù)驗(yàn)證結(jié)果\n); fprintf(距離%.1f 分鐘\n, dist_builtin); fprintf(路徑%s\n, num2str(path_builtin));這個(gè)簡(jiǎn)單的案例展示了如何將實(shí)際問(wèn)題抽象為圖并用Dijkstra算法求解。你可以很容易地將其擴(kuò)展例如從文件讀取更大的地圖數(shù)據(jù)或者將權(quán)重替換為實(shí)際的距離、時(shí)間、成本等。7. 常見(jiàn)問(wèn)題與調(diào)試技巧在實(shí)現(xiàn)和使用Dijkstra算法時(shí)你可能會(huì)遇到一些典型問(wèn)題。這里總結(jié)一份排查清單。問(wèn)題現(xiàn)象可能原因解決方案算法陷入死循環(huán)或結(jié)果明顯錯(cuò)誤如距離為Inf或01. 鄰接矩陣對(duì)角線未設(shè)為0。2. 圖包含負(fù)權(quán)重邊。3.visited數(shù)組邏輯錯(cuò)誤節(jié)點(diǎn)被重復(fù)訪問(wèn)或從未訪問(wèn)。4. 在松弛操作中錯(cuò)誤地包括了已訪問(wèn)節(jié)點(diǎn)。1. 確保adjMatrix(i,i)0。2. Dijkstra算法不能處理負(fù)權(quán)重。檢查輸入數(shù)據(jù)或考慮使用Bellman-Ford算法。3. 仔細(xì)檢查visited數(shù)組的更新邏輯確保節(jié)點(diǎn)只在被選為u后才標(biāo)記為visited。4. 在松弛循環(huán)中條件必須包含~visited(v)。路徑回溯函數(shù)reconstructPath進(jìn)入無(wú)限循環(huán)或路徑錯(cuò)誤1.prev數(shù)組初始化或更新有誤導(dǎo)致形成環(huán)路例如prev(i)i。2. 不可達(dá)節(jié)點(diǎn)的prev未正確標(biāo)記應(yīng)為0或NaN。3. 回溯終止條件有誤。1. 確保prev(src)0且算法中prev(v)只在dist(v)被更新時(shí)才被賦值為u。2. 初始化prev為0。在回溯函數(shù)中若prev(target)0 target~src則判定不可達(dá)。3. 終止條件應(yīng)為while u ~ 0或你設(shè)定的源點(diǎn)前驅(qū)標(biāo)識(shí)。對(duì)于大規(guī)模圖自定義實(shí)現(xiàn)速度極慢1. 使用了O(n2)的基礎(chǔ)循環(huán)版本。2. 鄰接矩陣過(guò)于稠密內(nèi)存和計(jì)算開(kāi)銷大。3. MATLAB循環(huán)本身較慢未向量化。1. 換用向量化版本或優(yōu)先隊(duì)列版本。2. 對(duì)于稀疏圖務(wù)必使用稀疏矩陣sparse存儲(chǔ)鄰接矩陣。將inf替換為0然后用G graph(sparse(adjMatrix))創(chuàng)建圖。這是性能提升的關(guān)鍵3. 盡可能使用邏輯索引和矩陣運(yùn)算替代for循環(huán)。內(nèi)置shortestpath函數(shù)報(bào)錯(cuò)1. 圖對(duì)象創(chuàng)建錯(cuò)誤例如權(quán)重包含負(fù)數(shù)、Inf或NaN。2. 指定的節(jié)點(diǎn)編號(hào)超出范圍。3. 對(duì)于digraph邊方向不符合預(yù)期。1. 創(chuàng)建圖對(duì)象前清理權(quán)重?cái)?shù)據(jù)w(w0) eps;將非正數(shù)設(shè)為一個(gè)極小正值或直接移除這些邊。2. 檢查s,t向量的最大值是否小于等于節(jié)點(diǎn)數(shù)。3. 確認(rèn)是有向圖還是無(wú)向圖邊的起點(diǎn)終點(diǎn)是否正確。自寫(xiě)算法與內(nèi)置函數(shù)結(jié)果有細(xì)微差異浮點(diǎn)數(shù)計(jì)算誤差累積。在比較距離alt dist(v)時(shí)使用的是嚴(yán)格小于。如果兩條路徑距離在浮點(diǎn)誤差內(nèi)相等選擇可能不同。這是正?，F(xiàn)象。如果必須完全一致可以在比較時(shí)加入一個(gè)容差if alt dist(v) - eps。但通常不影響實(shí)際應(yīng)用。調(diào)試技巧從小圖開(kāi)始用一個(gè)只有4-5個(gè)節(jié)點(diǎn)的、你手工能算出結(jié)果的圖來(lái)測(cè)試你的算法。打印出每次循環(huán)后的dist、visited和prev數(shù)組與你的手動(dòng)計(jì)算過(guò)程對(duì)比。使用MATLAB調(diào)試器在關(guān)鍵行設(shè)置斷點(diǎn)觀察變量狀態(tài)。特別是檢查選取最小節(jié)點(diǎn)u是否正確以及松弛操作是否按預(yù)期更新了鄰居?？梢暬瘜?duì)于小型圖用plot(graph(adjMatrix))把圖畫(huà)出來(lái)直觀地檢查邊和權(quán)重。用highlight函數(shù)標(biāo)出算法計(jì)算出的最短路徑看是否合理。性能剖析使用MATLAB的profile工具在命令行輸入profile on運(yùn)行你的函數(shù)再輸入profile viewer查看代碼的“熱點(diǎn)”即最耗時(shí)的部分針對(duì)性地優(yōu)化。實(shí)現(xiàn)Dijkstra算法是理解圖論算法和MATLAB矩陣編程的絕佳練習(xí)。從最基礎(chǔ)的雙重循環(huán)開(kāi)始逐步優(yōu)化到向量化操作最終過(guò)渡到使用成熟的內(nèi)置工具箱這個(gè)過(guò)程中對(duì)算法細(xì)節(jié)、數(shù)據(jù)結(jié)構(gòu)選擇和MATLAB語(yǔ)言特性的思考其價(jià)值遠(yuǎn)超過(guò)僅僅調(diào)通一個(gè)函數(shù)。當(dāng)你需要處理一個(gè)全新的、沒(méi)有現(xiàn)成工具的圖算法問(wèn)題時(shí)這段經(jīng)歷積累的經(jīng)驗(yàn)將至關(guān)重要。