圖論最短路問(wèn)題ppt課件(編輯修改稿)
2025-06-02 23:19 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 權(quán)，從 v 的父親標(biāo)記 )( vz 追溯到 u 0 , 就得到 u 0 到 v 的最短路的路線(xiàn) .（ 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例 求下圖從頂點(diǎn) u 1 到其余頂點(diǎn)的最短路．先寫(xiě)出帶權(quán)鄰接矩陣： ??????????????????????????????????03064093021509701608120W因 G 是無(wú)向圖，故 W 是對(duì)稱(chēng)陣． TO MATLAB (road1) )(iul迭代次數(shù) 1u 2u 3u 4u 5u 6u 7u 8u１2345678 ０ ? ? ? ? ? ? ? 0 ２ １ ８ ? ? ? ? 2 8 ? ? 10 ? 8 3 ? 10 ? 8 6 10 12 7 10 12 9 12 1 2最后標(biāo)記 :)( vl)( vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul 1u 2u 3u 4u 5u 6u 7u 8u最后標(biāo)記 :)( vl)( vz 0 2 1 7 3 6 9 1 2 1u 1u 1u 6u 2u 5u 4u 5uu1 u2 u3 u4 u5 u6 u7 u8 返回 每 對(duì) 頂 點(diǎn) 之 間 的 最 短 路 ( 二 ) 算法原理求距離矩陣的方法 求路徑矩陣的方法 查找最短路路徑的方法 （一）算法的基本思想 （三）算法步驟 返回 算法的基本思想 直接在圖的帶權(quán)鄰接矩陣中用插入頂點(diǎn)的方法依次構(gòu)造出 ? 個(gè)矩陣 D (1 ) 、 D (2 ) 、 … 、 D (? ) ，使最后得到的矩陣 D (? ) 成為圖的距離矩陣，同時(shí)也求出插入點(diǎn)矩陣以便得到兩點(diǎn)間的最短路徑．返回 算法原理 —— 求距離矩陣的方法 把帶權(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 (? ) 即是距離矩陣． 返回 算法原理 —— 求路徑矩陣的方法 R= ?? ?)( ijr , r ij 的含義是從 v i 到 v j 的最短路要經(jīng)過(guò)點(diǎn)號(hào)為 r ij 的點(diǎn)．?? ?? )( )0()0( ijrR , jr ij
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1