1. 項(xiàng)目概述從“最短路徑”到“圖論模型”的實(shí)戰(zhàn)跨越在數(shù)學(xué)建模和算法學(xué)習(xí)的路上圖論模型絕對是一個繞不開的硬核主題。它不像線性規(guī)劃那樣直觀也不像微分方程那樣有明確的物理背景但它的應(yīng)用場景卻無處不在——從我們手機(jī)里的地圖導(dǎo)航到社交網(wǎng)絡(luò)的好友推薦再到物流配送的路線規(guī)劃背后都有圖論的身影。而Dijkstra算法作為圖論中最經(jīng)典、最核心的算法之一是解決“單源最短路徑”問題的基石。很多同學(xué)在學(xué)習(xí)時往往止步于理解算法的偽代碼或手動演算幾個簡單例子一旦遇到復(fù)雜的真實(shí)數(shù)據(jù)或需要在Matlab中實(shí)現(xiàn)就感到無從下手。這篇內(nèi)容我就結(jié)合自己多次在數(shù)模競賽和實(shí)際項(xiàng)目中應(yīng)用Dijkstra算法的經(jīng)驗(yàn)來一次徹底的拆解。我們不只講算法原理更要聚焦于如何在Matlab這個強(qiáng)大的計算環(huán)境中將理論轉(zhuǎn)化為可運(yùn)行、可調(diào)試、可應(yīng)用于實(shí)際問題的代碼。你會發(fā)現(xiàn)掌握了這個模型你就擁有了一把解決網(wǎng)絡(luò)優(yōu)化類問題的萬能鑰匙。2. 圖論模型與Dijkstra算法的核心思想拆解2.1 圖論模型將世界抽象為點(diǎn)與線在開始敲代碼之前我們必須先建立正確的“圖”思維。圖論中的“圖”Graph不是指函數(shù)圖像而是由“頂點(diǎn)”Vertex或Node和“邊”Edge組成的抽象結(jié)構(gòu)。一個地鐵線路圖、一個計算機(jī)網(wǎng)絡(luò)拓?fù)洹⒁粋€論文引用關(guān)系都可以抽象成一個圖。圖的數(shù)學(xué)表示與Matlab存儲在Matlab中我們最常用的表示方法是鄰接矩陣。對于一個有n個頂點(diǎn)的圖我們可以用一個n×n的矩陣A來表示。A(i, j)的值表示從頂點(diǎn)i到頂點(diǎn)j的邊的權(quán)重。如果兩點(diǎn)之間沒有直接相連的邊通常用Inf無窮大或一個非常大的數(shù)來表示。對于無向圖邊沒有方向鄰接矩陣是對稱的即A(i, j) A(j, i)。注意這里有一個初學(xué)者極易混淆的點(diǎn)。在有些教材或代碼中會用0來表示沒有邊。但在Dijkstra算法的實(shí)現(xiàn)中強(qiáng)烈建議使用Inf。因?yàn)樗惴ǖ暮诵牟僮魇菍ふ易钚≈?會被誤認(rèn)為是一條代價為0的路徑從而導(dǎo)致邏輯錯誤。使用Inf能清晰地表示“不可達(dá)”狀態(tài)。為什么選擇鄰接矩陣雖然對于稀疏圖邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方鄰接表在存儲效率上更高但在Matlab中矩陣運(yùn)算是其核心優(yōu)勢向量化操作速度極快。對于數(shù)模競賽中常見的中等規(guī)模問題幾百到幾千個節(jié)點(diǎn)使用鄰接矩陣編寫出的代碼更加簡潔、直觀也更容易調(diào)試。我們優(yōu)先保證代碼的清晰度和可讀性這是快速建模和修改的關(guān)鍵。2.2 Dijkstra算法原理步步為營的“貪心”策略Dijkstra算法的目標(biāo)是在一個帶權(quán)有向圖權(quán)值為非負(fù)數(shù)中找到從一個指定的源點(diǎn)到圖中所有其他頂點(diǎn)的最短路徑及其長度。它的核心思想是一種“貪心”策略每次從未確定最短路徑的頂點(diǎn)集合中選擇一個距離源點(diǎn)最近的頂點(diǎn)認(rèn)為這個距離就是它的最終最短距離然后利用這個新確定的頂點(diǎn)去更新它所有鄰居頂點(diǎn)到源點(diǎn)的距離估計。我們可以用一個生活化的類比來理解想象你要去一個陌生的城市見多個朋友你只知道部分街道的通行時間。你的策略是從你所在的位置源點(diǎn)開始你只知道直接相連的朋友家的時間。你總是先去那個已知耗時最短的朋友家。到了這個朋友家后你可能會發(fā)現(xiàn)從他家去其他朋友家有更近的路于是你更新你對其他朋友家耗時的“最佳估計”。重復(fù)步驟2和3直到你確定了去所有朋友家的最短時間。這個“總是先處理當(dāng)前已知最近點(diǎn)”的策略就是Dijkstra算法保證正確性的關(guān)鍵在邊權(quán)非負(fù)的前提下。2.3 算法步驟的Matlab思維轉(zhuǎn)換標(biāo)準(zhǔn)的算法描述會用到兩個集合已確定最短路徑的頂點(diǎn)集合S和未確定的集合U。在Matlab實(shí)現(xiàn)時我們通常用幾個數(shù)組來模擬這個過程這樣更利于向量化操作初始化dist: 一個一維數(shù)組dist(i)表示從源點(diǎn)到頂點(diǎn)i的當(dāng)前已知最短距離估計。初始時源點(diǎn)設(shè)為0其他點(diǎn)設(shè)為Inf。visited: 一個邏輯數(shù)組visited(i)false表示頂點(diǎn)i的最短距離尚未最終確定。初始全為false。prev: 一個數(shù)組prev(i)記錄在最短路徑上頂點(diǎn)i的前驅(qū)頂點(diǎn)是誰。用于最后回溯出完整路徑。初始可以設(shè)為-1或0。主循環(huán)在所有visited為false的頂點(diǎn)中找到dist值最小的那個頂點(diǎn)u。這就是“貪心”選擇。將頂點(diǎn)u標(biāo)記為visited(u)true。此時dist(u)就是它的最終最短距離。松弛操作遍歷頂點(diǎn)u的所有鄰居v即A(u, v) Inf。如果通過u到v比當(dāng)前已知的路徑更短即dist(u) A(u, v) dist(v)那么就更新dist(v)為這個更小的值并記錄prev(v) u。循環(huán)結(jié)束當(dāng)所有頂點(diǎn)都被標(biāo)記為visited或剩余未訪問頂點(diǎn)的dist均為Inf時算法結(jié)束。dist數(shù)組存儲了從源點(diǎn)到所有點(diǎn)的最短距離prev數(shù)組存儲了路徑信息。Matlab實(shí)現(xiàn)的關(guān)鍵優(yōu)化尋找未訪問節(jié)點(diǎn)中dist最小值這一步如果使用循環(huán)遍歷時間復(fù)雜度是O(n)。在主循環(huán)n次的情況下總復(fù)雜度會成為O(n2)。對于稍大的圖這很慢。我們可以利用Matlab的向量化查找函數(shù)min但需要巧妙處理已訪問節(jié)點(diǎn)的排除。一種高效且清晰的做法是在查找時將已訪問節(jié)點(diǎn)的dist臨時設(shè)置為Inf這樣min函數(shù)就會自動忽略它們。3. Matlab實(shí)現(xiàn)Dijkstra算法的完整代碼與逐行解析理解了原理接下來就是實(shí)戰(zhàn)。下面我將給出一個功能完整、注釋清晰的Matlab函數(shù)實(shí)現(xiàn)并逐段解釋其設(shè)計意圖和細(xì)節(jié)。function [dist, path] myDijkstra(adjMatrix, src) % MYDIJKSTRA 使用Dijkstra算法計算單源最短路徑 % 輸入?yún)?shù) % adjMatrix: n x n 的鄰接矩陣adjMatrix(i,j)表示從i到j(luò)的邊權(quán)無邊時為Inf。 % src: 源點(diǎn)編號1 src n % 輸出參數(shù) % dist: 1 x n 向量dist(i)是從源點(diǎn)到節(jié)點(diǎn)i的最短距離。 % path: 1 x n 的元胞數(shù)組path{i}是從源點(diǎn)到節(jié)點(diǎn)i的最短路徑節(jié)點(diǎn)序列。 % % 示例 % A [0 2 Inf 1 8; % 2 0 1 Inf 3; % Inf 1 0 4 Inf; % 1 Inf 4 0 2; % 8 3 Inf 2 0]; % [d, p] myDijkstra(A, 1); % disp(到節(jié)點(diǎn)5的最短距離), disp(d(5)) % disp(路徑), disp(p{5}) n size(adjMatrix, 1); % 圖的頂點(diǎn)數(shù) dist inf(1, n); % 初始化距離數(shù)組為無窮大 visited false(1, n); % 訪問標(biāo)記數(shù)組 prev zeros(1, n); % 前驅(qū)節(jié)點(diǎn)數(shù)組用于回溯路徑 % 初始化源點(diǎn) dist(src) 0; prev(src) -1; % 源點(diǎn)的前驅(qū)設(shè)為-1表示路徑起點(diǎn) % 主循環(huán)最多循環(huán)n次 for i 1:n % 步驟1在所有未訪問節(jié)點(diǎn)中找到當(dāng)前距離最小的節(jié)點(diǎn)u % 技巧將已訪問節(jié)點(diǎn)的距離臨時設(shè)為Inf這樣min函數(shù)就會自動跳過它們 tempDist dist; tempDist(visited) inf; [~, u] min(tempDist); % 如果剩余的最小距離都是Inf說明剩下的節(jié)點(diǎn)不可達(dá)可以提前結(jié)束 if isinf(tempDist(u)) break; end % 標(biāo)記節(jié)點(diǎn)u為已訪問 visited(u) true; % 步驟2松弛操作 - 更新u的所有鄰居節(jié)點(diǎn)的距離 % 找到u的所有鄰居即邊權(quán)不是Inf的節(jié)點(diǎn) neighbors find(~isinf(adjMatrix(u, :)) ~visited); for v neighbors alt dist(u) adjMatrix(u, v); if alt dist(v) dist(v) alt; % 更新最短距離估計 prev(v) u; % 記錄前驅(qū)節(jié)點(diǎn) end end end % 步驟3根據(jù)prev數(shù)組回溯構(gòu)造最短路徑 path cell(1, n); for target 1:n if isinf(dist(target)) path{target} []; % 不可達(dá) else % 從目標(biāo)節(jié)點(diǎn)反向回溯到源點(diǎn) seq target; while prev(seq) 0 seq [prev(seq), seq]; % 將前驅(qū)節(jié)點(diǎn)加到序列前面 end path{target} seq; end end end代碼解析與關(guān)鍵點(diǎn)輸入驗(yàn)證雖未寫出但很重要一個健壯的函數(shù)應(yīng)該檢查adjMatrix是否為方陣src是否在有效范圍內(nèi)以及邊權(quán)是否包含負(fù)數(shù)Dijkstra算法不能處理負(fù)權(quán)邊。在實(shí)際數(shù)模比賽中如果數(shù)據(jù)已知合規(guī)可以省略以保持簡潔若是通用函數(shù)則必須加上。tempDist的妙用這是實(shí)現(xiàn)中的一個小技巧。為了用min函數(shù)找到未訪問節(jié)點(diǎn)中的最小值我們創(chuàng)建了tempDist副本并將已訪問節(jié)點(diǎn)的距離設(shè)為Inf。這比寫一個循環(huán)去判斷visited狀態(tài)要簡潔高效得多充分利用了Matlab的向量化特性。提前終止條件if isinf(tempDist(u))這一判斷非常有用。當(dāng)圖不是連通圖時源點(diǎn)可能無法到達(dá)所有節(jié)點(diǎn)。此條件可以避免無謂的循環(huán)提升效率。松弛操作的向量化潛力當(dāng)前的松弛操作使用了一個for循環(huán)遍歷鄰居。對于性能要求極高的場景可以嘗試向量化。但考慮到代碼的清晰度和可讀性在鄰居數(shù)不多的情況下for循環(huán)更容易理解和調(diào)試。這是數(shù)模競賽中“可讀性優(yōu)先于極端優(yōu)化”的典型體現(xiàn)。路徑回溯path的輸出格式設(shè)計為元胞數(shù)組因?yàn)榈矫總€目標(biāo)節(jié)點(diǎn)的路徑長度不同。回溯時從目標(biāo)節(jié)點(diǎn)開始不斷查找prev數(shù)組直到源點(diǎn)prev為-1。注意seq [prev(seq), seq]這句它將新找到的前驅(qū)節(jié)點(diǎn)插入序列頭部最終得到的路徑順序是從源點(diǎn)到目標(biāo)點(diǎn)。4. 從算法到模型在數(shù)學(xué)建模中的實(shí)戰(zhàn)應(yīng)用掌握了算法實(shí)現(xiàn)我們更要解決“何時用”和“怎么用”的問題。Dijkstra算法在數(shù)學(xué)建模中絕非僅僅用于計算地圖距離。4.1 經(jīng)典應(yīng)用場景拓展交通網(wǎng)絡(luò)規(guī)劃最直接的應(yīng)用。頂點(diǎn)是交通樞紐車站、路口邊權(quán)可以是距離、時間、費(fèi)用或綜合成本。問題可能是救災(zāi)物資從倉庫到所有受災(zāi)點(diǎn)的最短時間路徑、公交線路優(yōu)化等。建模要點(diǎn)關(guān)鍵在于邊權(quán)的定義。時間權(quán)重可能隨擁堵程度變化這就需要引入動態(tài)圖或分段函數(shù)增加了復(fù)雜度。通信網(wǎng)絡(luò)路由在網(wǎng)絡(luò)中數(shù)據(jù)包需要選擇最優(yōu)路徑傳輸。頂點(diǎn)是路由器或交換機(jī)邊權(quán)可以是鏈路延遲、丟包率或帶寬的倒數(shù)。建模要點(diǎn)可能需要考慮多約束最短路徑比如同時要求延遲低和丟包率小。這時單一的Dijkstra可能不夠需要引入多目標(biāo)優(yōu)化或權(quán)重綜合函數(shù)。社交網(wǎng)絡(luò)“影響力”傳播在社交網(wǎng)絡(luò)中我們可以研究信息傳播的最短路徑。頂點(diǎn)是用戶邊權(quán)可以定義為兩個用戶之間的“社交距離”如親密度的倒數(shù)。Dijkstra算法可以找出從某個種子用戶出發(fā)信息傳播到其他用戶的“最短關(guān)系鏈”。建模要點(diǎn)圖的構(gòu)建是難點(diǎn)。如何從復(fù)雜的社交互動數(shù)據(jù)點(diǎn)贊、評論、轉(zhuǎn)發(fā)中量化出合理的邊權(quán)需要結(jié)合具體問題設(shè)計。項(xiàng)目管理中的關(guān)鍵路徑變形應(yīng)用雖然關(guān)鍵路徑法通常用拓?fù)渑判虻珜⑵湟暈橐粋€有向無環(huán)圖DAG邊權(quán)為任務(wù)時長求從起點(diǎn)到終點(diǎn)的最長路徑其思想與最短路徑有相通之處。可以用類似Dijkstra的方法有時稱為“最長路徑算法”在DAG上有效來求解。建模要點(diǎn)需要先將任務(wù)依賴關(guān)系轉(zhuǎn)化為圖結(jié)構(gòu)。4.2 一個建模案例城市應(yīng)急物資配送中心選址問題簡述某城市有多個居民區(qū)需求點(diǎn)和幾個候選的物資倉庫地址。我們需要選擇一個倉庫位置使得從該倉庫到最遠(yuǎn)居民區(qū)的運(yùn)輸時間最短。這就是經(jīng)典的“中心點(diǎn)”問題。如何與Dijkstra結(jié)合建圖將城市道路交叉口和居民區(qū)、候選倉庫都抽象為圖的頂點(diǎn)。根據(jù)道路實(shí)際數(shù)據(jù)長度、限速計算邊權(quán)通行時間。計算對每一個候選倉庫作為源點(diǎn)運(yùn)行一次Dijkstra算法得到它到所有居民區(qū)的最短時間。分析對于每個倉庫的結(jié)果找出到所有居民區(qū)中最長的那個時間即“最壞情況”響應(yīng)時間。決策比較所有候選倉庫的“最壞情況響應(yīng)時間”選擇其中最小值對應(yīng)的倉庫作為最優(yōu)選址。% 假設(shè)adjMatrix是城市路網(wǎng)鄰接矩陣demandNodes是居民區(qū)節(jié)點(diǎn)索引數(shù)組candidateSites是候選倉庫節(jié)點(diǎn)索引數(shù)組 worstCaseTime inf; % 初始化最優(yōu)的最壞情況時間 bestSite -1; % 初始化最優(yōu)倉庫位置 for site candidateSites [distances, ~] myDijkstra(adjMatrix, site); % 獲取到所有居民區(qū)的距離 timesToDemands distances(demandNodes); % 計算最壞情況時間 currentWorstTime max(timesToDemands); if currentWorstTime worstCaseTime worstCaseTime currentWorstTime; bestSite site; end end fprintf(最優(yōu)倉庫選址為節(jié)點(diǎn) %d其最遠(yuǎn)居民區(qū)響應(yīng)時間為 %.2f 小時。\n, bestSite, worstCaseTime);這個案例展示了Dijkstra算法如何作為一個核心計算模塊嵌入到一個更大的決策模型中。在數(shù)學(xué)建模論文中你需要清晰地闡述這個轉(zhuǎn)換過程實(shí)際問題 - 圖論模型 - 算法選擇 - 求解 - 結(jié)果解釋。5. 性能優(yōu)化、常見問題與調(diào)試技巧5.1 當(dāng)圖很大時效率優(yōu)化思路我們實(shí)現(xiàn)的myDijkstra函數(shù)時間復(fù)雜度約為O(n2)對于節(jié)點(diǎn)數(shù)n上萬的大型圖如全國路網(wǎng)會非常慢。在數(shù)模競賽中如果遇到大數(shù)據(jù)需要考慮優(yōu)化。使用稀疏矩陣存儲如果圖是稀疏的邊數(shù)遠(yuǎn)小于n2使用Matlab的sparse矩陣存儲鄰接矩陣可以極大節(jié)省內(nèi)存并且某些矩陣操作會更快。% 假設(shè)我們有邊的列表I, J, W 分別表示起點(diǎn)、終點(diǎn)、權(quán)重數(shù)組 sparseAdj sparse(I, J, W, n, n); % 使用 sparseAdj 作為 myDijkstra 的輸入需要修改函數(shù)內(nèi)部對鄰接矩陣的訪問方式支持稀疏索引注意直接使用我們之前的myDijkstra函數(shù)可能需要對adjMatrix(u, :)這樣的整行訪問做調(diào)整因?yàn)閷ο∈杈仃囌胁僮餍士赡懿桓摺８咝У淖龇ㄊ窃跇?gòu)建稀疏矩陣時也構(gòu)建一個鄰接表結(jié)構(gòu)。使用優(yōu)先隊(duì)列最小堆標(biāo)準(zhǔn)Dijkstra算法的高效實(shí)現(xiàn)依賴于優(yōu)先隊(duì)列來快速提取未訪問節(jié)點(diǎn)中的最小距離節(jié)點(diǎn)。Matlab沒有內(nèi)置的堆數(shù)據(jù)結(jié)構(gòu)但可以自己實(shí)現(xiàn)或者使用較新的min函數(shù)對部分?jǐn)?shù)據(jù)進(jìn)行操作。更專業(yè)的做法是調(diào)用用C/C編寫并編譯好的Mex函數(shù)但這在限時比賽中不現(xiàn)實(shí)。利用Matlab內(nèi)置函數(shù)新版本的Matlab圖論工具箱graph和digraph對象功能強(qiáng)大其shortestpath或distances函數(shù)底層經(jīng)過了高度優(yōu)化對于大型稀疏圖效率遠(yuǎn)超自編的O(n2)代碼。% 使用內(nèi)置圖論工具箱 G graph(adjMatrix); % 將鄰接矩陣轉(zhuǎn)換為graph對象 [dist, path] shortestpath(G, src, target); % 計算單源單目標(biāo) allDist distances(G, src); % 計算單源所有目標(biāo)距離在數(shù)模競賽中的建議如果比賽允許使用工具箱且問題規(guī)模較大強(qiáng)烈推薦直接使用內(nèi)置函數(shù)。你的核心工作是建模和結(jié)果分析而不是重復(fù)造輪子。自編算法的意義在于理解原理和應(yīng)對無法使用工具箱的特殊情況。5.2 常見錯誤與調(diào)試技巧負(fù)權(quán)邊Dijkstra算法不能處理含有負(fù)權(quán)重的邊。如果圖中存在負(fù)權(quán)邊算法會得出錯誤結(jié)果。此時應(yīng)使用Bellman-Ford或SPFA算法。在讀取數(shù)據(jù)后務(wù)必用min(adjMatrix(adjMatrix ~ Inf))檢查是否有負(fù)值。自環(huán)與平行邊自環(huán)從自己到自己的邊通常權(quán)重為0不影響。平行邊兩點(diǎn)間有多條邊在構(gòu)建鄰接矩陣時需要決定保留哪一條。通常保留權(quán)重最小的一條作為A(i,j)的值。路徑回溯錯誤最常見的錯誤是prev數(shù)組初始化或更新邏輯有誤。調(diào)試時可以找一個5-6個節(jié)點(diǎn)的小圖手動模擬算法運(yùn)行每一步都打印出dist,visited,prev數(shù)組的值與你的代碼輸出進(jìn)行比對。這是最有效的調(diào)試方法。Inf的使用確保你的鄰接矩陣中“無邊”用Inf表示并且在做加法dist(u) A(u,v)時Matlab的Inf 有限值 Inf的特性會正常工作。如果錯誤地用0或-1表示無邊加法運(yùn)算會導(dǎo)致邏輯混亂。節(jié)點(diǎn)編號Matlab索引從1開始。如果你的原始數(shù)據(jù)節(jié)點(diǎn)編號從0開始必須在構(gòu)建鄰接矩陣前將其轉(zhuǎn)換為1-based。5.3 結(jié)果可視化讓輸出更直觀在論文中一圖勝千言。Matlab提供了強(qiáng)大的繪圖功能來可視化圖結(jié)構(gòu)和最短路徑。% 假設(shè)我們有一個圖G和從源點(diǎn)src到目標(biāo)點(diǎn)target的最短路徑節(jié)點(diǎn)序列shortestPathNodes figure; h plot(G, NodeLabel, 1:numnodes(G), EdgeLabel, G.Edges.Weight, LineWidth, 1.5); highlight(h, shortestPathNodes, NodeColor, r, EdgeColor, r, LineWidth, 3); title(sprintf(從節(jié)點(diǎn)%d到節(jié)點(diǎn)%d的最短路徑, src, target));這段代碼會繪制出整個圖并用高亮的紅色線條和節(jié)點(diǎn)標(biāo)記出最短路徑。在建模論文中這樣的可視化結(jié)果能極大提升表現(xiàn)力清晰地向評委展示你的求解成果。6. 超越單源最短路徑算法的變體與模型拓展掌握了基礎(chǔ)的Dijkstra你的圖論工具箱才剛剛打開。很多復(fù)雜問題可以在此基礎(chǔ)上進(jìn)行拓展。多源最短路徑如果需要計算所有頂點(diǎn)對之間的最短路徑可以對每個頂點(diǎn)都作為源點(diǎn)運(yùn)行一次Dijkstra算法時間復(fù)雜度O(n3)。對于稠密圖Floyd-Warshall算法動態(tài)規(guī)劃在實(shí)現(xiàn)上更簡潔也是O(n3)。在Matlab中可以簡單寫一個循環(huán)調(diào)用myDijkstra。k最短路徑有時我們不僅需要最短路徑還需要第二短、第三短的路徑例如在交通規(guī)劃中提供備選方案。這需要在Dijkstra算法的基礎(chǔ)上進(jìn)行修改使用“偏離路徑”或“Yens algorithm”等思想。帶約束的最短路徑例如在預(yù)算限制下找最短路徑費(fèi)用距離雙目標(biāo)或者找時間窗約束下的最快路徑。這通常需要將其建模為更復(fù)雜的優(yōu)化問題如整數(shù)規(guī)劃或者使用標(biāo)號法、啟發(fā)式算法如A算法進(jìn)行求解。A算法可以看作是Dijkstra的改進(jìn)通過引入一個到目標(biāo)點(diǎn)的啟發(fā)式估計如直線距離來優(yōu)先搜索更有希望的方向從而大幅減少搜索范圍在路徑規(guī)劃中極為高效。從模型到代碼再從代碼回到模型這個閉環(huán)是數(shù)學(xué)建模能力的核心。Dijkstra算法提供了一個完美的范例。它要求你首先抽象化現(xiàn)實(shí)問題然后用嚴(yán)謹(jǐn)?shù)臄?shù)據(jù)結(jié)構(gòu)圖表示接著理解并實(shí)現(xiàn)一個精巧的算法最后將計算結(jié)果詮釋回現(xiàn)實(shí)意義。在Matlab中實(shí)現(xiàn)它不僅能加深你對算法本身的理解更能鍛煉你將數(shù)學(xué)思想轉(zhuǎn)化為計算實(shí)踐的綜合能力。下次當(dāng)你遇到網(wǎng)絡(luò)、路徑、關(guān)系類的問題時不妨先想一想這能不能畫成一張圖