數(shù)模最短路與最優(yōu)問題-全文預(yù)覽
【正文】 ? ( e ), 則稱 G 1 是 G 的 子圖 ． 特別的，若 V 1 = V ，則 G 1 稱為 G 的 生成子圖 ． ( 2 ) 設(shè) V 1 ? V ，且 V 1 ?? ，以 V 1 為頂點(diǎn)集、兩個(gè)端點(diǎn)都在 V 1 中的 圖 G 的邊為邊集的圖 G 的子圖，稱為 G 的 由 V 1 導(dǎo)出的子圖 ，記為 G [ V 1 ]. ( 3 ) 設(shè) E 1 ? E , 且 E 1 ?? , 以 E 1 為邊集 , E 1 的端點(diǎn)集為頂點(diǎn)集的圖 G 的子圖 , 稱為 G 的 由 E 1 導(dǎo)出的子圖 , 記為 G [ E 1 ]. G G [{ v 1 ,v 4 ,v 5 }] G [{ e1 ,e 2 ,e 3 }] 返回 關(guān)聯(lián)矩陣 對(duì)無向圖 Ｇ ，其關(guān)聯(lián)矩陣 Ｍ ＝?? ?)( ijm，其中： 10ijijijvemve?? ??若 與 相 關(guān) 聯(lián)若 與 不 關(guān) 聯(lián) M =43215432110110011000101110001vvvveeeee?????????????? 對(duì)有向圖Ｇ，其關(guān)聯(lián)矩陣 Ｍ ＝?? ?)( ijm，其中： ???????不關(guān)聯(lián)與若的終點(diǎn)是若的起點(diǎn)是若jijijiijevevevm011 注：假設(shè)圖為無向簡(jiǎn)單圖 返回 鄰接矩陣 對(duì)無向圖 Ｇ ，其鄰接矩陣?? ?? )( ijaA，其中： 不相鄰與若相鄰與若jijiij vvvva???? 01 注：假設(shè)圖為簡(jiǎn)單無向圖 A =432143210111101011011010vvvvvvvv?????????????? 對(duì)有向圖 Ｇ ＝（ Ｖ ， Ｅ ），其鄰接矩陣?? ?? )( ijaA，其中： EvvEvvajijiij ?????? ），若（），若（01 對(duì)有向賦權(quán)圖 Ｇ ，其鄰接矩陣?? ?? )( ijaA，其中： ??????????EvvjiwEvvwajiijjiijij),(0,),(若若為其權(quán)且若 無向賦權(quán)圖的鄰接矩陣可類似定義．A =4321432105375083802720vvvvvvvv???????????????? 返回 最 短 路 問 題 及 其 算 法 一、 基 本 概 念 二、固 定 起 點(diǎn) 的 最 短 路 三、每 對(duì) 頂 點(diǎn) 之 間 的 最 短 路 返回 基 本 概 念 通路 44112544141vevevevevW vv ?道路 4332264521141vevevevevevT vv ?路徑 4521141vevevP vv ?定義１ 在無向圖 G =( V , E , ? ) 中： （１） 頂點(diǎn)與邊相互交錯(cuò)且iii vve 1)( ??? ( i =1,2 , … , k ) 的有限非空序列 )( 12110 kkk vevevevw ?? ? 稱為一條從 0v 到 kv 的 通路 ，記為kvvW 0 （２）邊不重復(fù)但頂點(diǎn)可重復(fù)的通路稱為 道路 ，記為kvvT 0 （３）邊與頂點(diǎn)均不重復(fù)的通路稱為 路徑 ，記為kvvP 0 定義２ （１）任意兩點(diǎn)均有路徑的圖稱為 連通圖 ． （２）起點(diǎn)與終點(diǎn)重合的路徑稱為 圈 ． （３）連通而無圈的圖稱為 樹 ．定義３ （１）設(shè)( , )P u v是賦權(quán)圖 G 中從 u 到 v 的路徑， 則稱???)()()(PEeewPw為路徑 P 的 權(quán) ． ( 2) 在賦權(quán)圖 G 中，從頂點(diǎn) u 到頂點(diǎn) v 的具有最小權(quán)的路 ( , )P u v?，稱為 u 到 v 的 最短路 ． 返回 固 定 起 點(diǎn) 的 最 短 路 最短路是一條路徑，且最短路的任一段也是最短路． 假設(shè)在 u0v0的最短路中只取一條，則從 u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以 u0為根的樹． 因此 , 可采用樹生長(zhǎng)的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路． 6 2 3 4 1 5 8 7 Di j k s t r a 算法 ：求 G 中從頂點(diǎn) 0u 到其余頂點(diǎn)的最短路 . 設(shè) G 為賦權(quán)有向圖或無向圖， G 邊上的權(quán)均非負(fù)． 對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（ l v( ) ， z v( ) ），其中 : l v( ) ：表從頂點(diǎn)0u到 v 的一條路的權(quán)． z v( ) ： v 的父親點(diǎn)，用以確定最短路的路線 算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終 l v( ) 為從頂點(diǎn)0u 到 v 的最短路的權(quán)． S ：具有永久標(biāo)號(hào)的頂點(diǎn)集 輸入 : 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 中的頂點(diǎn)，則令 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 例 求下圖從頂點(diǎn) u 1 到其余頂點(diǎn)的最短路． 先寫出帶權(quán)鄰接矩陣： ??????????????????????????????????03064093021509701608120W 因 G 是無向圖，故 W 是對(duì)稱 矩 陣． TO MATLAB(road1) )( iul 迭代 次數(shù) 1u 2u 3u 4u 5u 6u 7u 8u １ 2 3 4 5 6 7 8 ０ ? ? ? ? ? ? ? ２ １ ８ ? ? ? ? 2 8 ? ? 10 ? 8 3 ? 10 ? 8 6 10 12 7 10 12 9 1 2 12 最后標(biāo)記 : )( vl )( vz 0 2 1 7 3 6 9 1 2 1u 1u 1u 6u 2u 5u 4u 5u ??????????????????????????????????03064093021509701608120Wl u W u v( ) ( , )? )( iul 1u 2u 3u 4u 5u 6u 7u 8u 最后標(biāo)記 : )( vl )( vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1