短路問題實驗ppt課件(已修改)
2025-05-13 22:13 本頁面
【正文】 數(shù)學(xué)模型與數(shù)學(xué)實驗 圖論模型 實驗?zāi)康? 實驗內(nèi)容 會用 Matlab軟件求最短路 了解最短路的算法及其應(yīng)用 圖 論 的 基 本 概 念 最 短 路 問 題 及 其 算 法 最 短 路 的 應(yīng) 用 實驗作業(yè) 固 定 起 點 的 最 短 路 最短路是一條路徑，且最短路的任一段也是最短路． 假設(shè)在 u0v0的最短路中只取一條，則從 u0到其余頂點的最短路將構(gòu)成一棵以 u0為根的樹． 因此 , 可采用樹生長的過程來求指定頂點到其余頂點的最短路． Di j k s t r a 算法 ：求 G 中從頂點 u 0 到其余頂點的最短路 設(shè) G 為賦權(quán)有向圖或無向圖， G 邊上的權(quán)均非負(fù)． 對每個頂點，定義兩個標(biāo)記（ l v( ) ， z v( ) ），其中 : l v( ) ：表從頂點 u 0 到 v 的一條路的權(quán)． z v( ) ： v 的父親點，用以確定最短路的路線 算法的過程就是在每一步改進(jìn)這兩個標(biāo)記，使最終 l v( ) 為從頂點u 0 到 v 的最短路的權(quán)． S ：具有永久標(biāo)號的頂點集 輸入 : G 的帶權(quán)鄰接矩陣 ),( vuw 算法步驟： （１）賦初值：令 S ＝ { u 0 } , l u( )0 =0 ? ? ?v S V S\ , 令 l v( ) = W u v( , )0 , z v( ) = u 0 u ? u 0 （ 3 ） 設(shè) v * 是使 l v( ) 取最小值的 S 中的頂點，則令 S =S ∪ { v * } ， u ? v * （ 4 ） 若 S ? φ ，轉(zhuǎn) 2 ，否則，停止 . 用上述算法求出的 l v( ) 就是 u 0 到 v 的最短路的權(quán)，從 v 的父親標(biāo)記)( vz 追溯到 u 0 , 就得到 u 0 到 v 的最短路的路線 . （ 2 ）更新 l v( ) 、 z v( ) ： ? ? ?v S V S\ , 若 l v( ) l u W u v( ) ( , )? 則令 l v( ) = l u W u v( ) ( , )? , z v( ) = u 例 求下圖從頂點 u 1 到其余頂點的最短路． 先寫出帶權(quán)鄰接矩陣： ??????????????????????????????????03064093021509701608120W 因 G 是無向圖，故 W 是對稱陣． )(iul迭代次數(shù) 1u 2u 3u 4u 5u 6u 7u 8u１234567
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1