圖論例子存檔北郵信通院陳鑫林教授授課PPT

1、 若干補(bǔ)充Ford(1956)-Moore(1957)-Bellman(1958) 算法由于Dijkstra算法只適用于弧長為正的情形,而Ford(1956)-Moore(1957)-Bellman(1958)算法適用于弧長可為負(fù),但不含負(fù)的有向回路的情形,并且在許多通信的論文中得到廣泛應(yīng)用,所以特做介紹.1Ford(1956)-Moore(1957)-Bellman(1958)算法它適用于弧長可為負(fù),但不含負(fù)的有向回路的情形.算法思路:從s到j(luò)至多k+1條弧的最短有向路徑可以由從s到j(luò)至多含k條弧的最短路徑得到.因此,在第k次迭代結(jié)束時(shí),節(jié)點(diǎn)的標(biāo)記就表示從s出發(fā)的含不多于k+1條弧的最短路徑

2、的長度.設(shè) 是給定的有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)G(V,E,l)中從s到j(luò)的不多于k條弧的最短有向路徑的長度,首先設(shè)2顯然,從s到j(luò)至多含k+1條弧的最短有向路徑可能由k+1條弧或較少的弧構(gòu)成,若它正好含k+1條弧,則設(shè)(i,j)是 中的最后一條弧,那么 可以看成是由從s到i的含k條弧的最短路徑 和后續(xù)弧(i,j)構(gòu)成,因此得 的長度是如果 含k條或較少的弧,則 .因此對kn, 時(shí),算法終止.如果在k=n-1時(shí)對某個(gè)j有 ,那么網(wǎng)中必有負(fù)向回路,算法失效,并在第n-1次迭代時(shí)終止.表明有負(fù)向回路.算法的計(jì)算復(fù)雜度為3例4567算法在k=4n=7次迭代終止.82.Floyd算法在以下情況可以簡化:(1)如有

3、度數(shù)為1的端,可把它們?nèi)サ粼僮鲇?jì)算;設(shè) 為度數(shù)為1的端,它只與 相連,則 與其它端的最短徑必經(jīng) ,所以(2)如有度數(shù)為2的端,則按下述方法去掉:設(shè) 為度數(shù)為2的端,它只與 相連,若 ,則可簡單地去掉若 ,也可去掉 ,但把 改成 9不論那種情況,與其它端間的最短徑長用下述公式計(jì)算:(3)稀疏網(wǎng)的情況下可把全圖分成幾個(gè)部分來計(jì)算,然后合并.當(dāng)網(wǎng)的邊數(shù)遠(yuǎn)少于全聯(lián)網(wǎng)的邊數(shù)時(shí),稱稀疏網(wǎng).此時(shí)往往存在割端或端數(shù)較少的割端.對于有割端 的網(wǎng)G,去掉后就把G分成幾部分(例如三部分G1,G2,G3),用Floyd算法分別求出的最短距離陣 及路由陣.若則 間最短距離為10例1112131415(3)次短徑和可用徑

4、:若兩端間有幾條徑,其中P1為最短徑,而P2與P1無公共邊卻有公共端,則稱P2不共邊徑或邊分離徑;若P3與P1除起終點(diǎn)外無公共端(必?zé)o公共邊),則稱P3為不共端徑或端分離徑.求次短徑的方法1)對不共邊徑從圖中去掉最短徑的所有邊,然后在剩下的圖中求最短徑;2)對不共端徑從圖中去掉最短徑的所有中間端(當(dāng)然段的關(guān)聯(lián)邊也去掉),然后在剩下的圖中求最短徑;16這個(gè)過程還可繼續(xù)下去.例:17從 到 有三條徑:18邊分離的次短徑19端分離的次短徑20可用徑在某些應(yīng)用中,要求找一批滿足條件的徑.當(dāng)有幾個(gè)條件時(shí),可先用一個(gè)條件求可用徑,再在其中篩選出滿足其它條件的可用徑.今用限制條件為徑長的例子來說明算法:仍用上圖,要求徑的長度小于M(=7)的可用徑.1)用F算法求出圖的最短徑長矩陣W和轉(zhuǎn)接矩陣R;2)若 ,則無可用徑, 若 ,則找一個(gè) 的鄰接節(jié)點(diǎn) ,如果 則排除,否則就得一可用徑21本例的距離矩陣,最短路徑和轉(zhuǎn)接矩陣分別如下22是可用徑.再看V1與V3能否延續(xù)23與V1相連的有V2,與V3相連的有V2.與V2相連的有V4.2425(4)圖的中心和中點(diǎn)從端間最短距離出發(fā)可定義網(wǎng)的中心,中點(diǎn)和直徑一個(gè)端 在網(wǎng)內(nèi)的位置可用最長的最短徑表示: 的最小值所對應(yīng)的端定義為網(wǎng)的中心:網(wǎng)