數(shù)學(xué)模型floyd算法(存儲(chǔ)版)
【正文】 inty Theory Laboratory 1 最 短 路 算 法 任意一對(duì)頂點(diǎn)之間的最短路算法 :Floyd算法 數(shù)學(xué)模型與實(shí)驗(yàn) Tsinghua University Uncertainty Theory Laboratory 2 ( 二 ) 算法原理求距離矩陣的方法 求路徑矩陣的方法 查找最短路路徑的方法 （一）算法的基本思想 （三）算法步驟 數(shù)學(xué)模型與實(shí)驗(yàn) Tsinghua University Uncertainty Theory Laboratory 3 算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出 ? 個(gè)矩陣 D (1 ) 、 D (2 ) 、 … 、 D (? ) ，使最后得到的矩陣 D (? )成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑． 數(shù)學(xué)模型與實(shí)驗(yàn) Tsinghua University Uncertainty Theory Laboratory 4 算法原理 —— 求距離矩陣的方法 把帶權(quán)鄰接矩陣 W 作為距離矩陣的初值，即 D ( 0 ) = ?? ?)( )0(ijd =W（１） D ( 1 ) = ?? ?)( )1(ijd ，其中 )0(1)0()1( ,m i n { iijij ddd ? })0(1 jd?)1(ijd 是從 v i 到 v j 的只允許以 v 1 作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．（ 2 ） D ( 2 ) = ?? ?)( )2(ijd ，其中 )1( 2)1()2( ,m i n { iijij ddd ? })1(2 jd? )2(ijd 是從 v i 到 v j 的只允許以 v 1 、 v 2 作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．…（ ? ） D (? ) = ????)()(ijd ，其中)1()1()( ,m i n { ??? ????iijij ddd })1( ?? ?? jd)( ?ijd 是從 v i 到 v j 的只允許以 v 1 、 v 2 、 … 、 ?v 作為中間點(diǎn)的路徑中最短路的長(zhǎng)度．即是從 v i 到 v j 中間可插入任何頂點(diǎn)的路徑中最短路的長(zhǎng)，因此D (? ) 即是距離矩陣． 數(shù)學(xué)模型與實(shí)驗(yàn) Tsinghua Un
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1