《短路問(wèn)題》ppt課件

《《短路問(wèn)題》ppt課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第二節(jié)最短路問(wèn)題§2.1基本概念與基本定理§2.2最短路的算法精品課程《運(yùn)籌學(xué)》第二節(jié)最短路問(wèn)題最短路問(wèn)題是重要的最優(yōu)化問(wèn)題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問(wèn)題，如管道鋪設(shè)、線路選擇，設(shè)備更新、投資等問(wèn)題，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問(wèn)題。精品課程《運(yùn)籌學(xué)》§2.1基本概念與基本定理在有向圖G中，設(shè)P是有向圖D=（V，E）中從頂點(diǎn)u到v為點(diǎn)弧交替的序列。如果序列中每一條弧的始點(diǎn)和終點(diǎn)恰好分別是與它前后相鄰的頂點(diǎn)，則稱這個(gè)序列P是D中的一條路。精品課程《運(yùn)籌學(xué)》設(shè)已給定了

2、一個(gè)有向賦權(quán)圖D=(V,A,w);wij≥0,((u,v)∈A)，若u是D中的一條路，則稱w(u)=∑wij為路u的總權(quán)數(shù)（或稱為路長(zhǎng)）。設(shè)u,v是D=(V,A,w)中取定的兩個(gè)點(diǎn)，存在從u到v的路，稱從u到v的路中總權(quán)數(shù)最小者為最短路。對(duì)于最短路，顯然有下列定理成立.精品課程《運(yùn)籌學(xué)》定理6.2.1有向圖D=(V,A,w)，V={1,2,..,n}，記dj為點(diǎn)1到點(diǎn)j的最短路的路長(zhǎng)且不妨設(shè)當(dāng)1＜i＜j時(shí)有0＜di＜dj＜∞,則有d1=0及dj=min{di+wij}(j=1,2,…,n),其中wi

3、j為點(diǎn)i到點(diǎn)j的弧的權(quán)數(shù)。精品課程《運(yùn)籌學(xué)》§2.2最短路的算法1．Dijkstra算法（適用于所有權(quán)非負(fù)的情況）Dijkstra算法是E.W.Dijkstra于1959年提出的，是目前公認(rèn)的對(duì)所有權(quán)非負(fù)的情況的最好算法。精品課程《運(yùn)籌學(xué)》設(shè)D=(V,A,w)滿足上述定理?xiàng)l件，則有以下算法：①令u1=0,uj﹦wij(若不存在點(diǎn)1到點(diǎn)j的路則記w1j=∞),p={1},T={2,3,…,n}(p為以確定的點(diǎn)之集，T為未確定的點(diǎn)之集)；②（指出永久標(biāo)號(hào)）在T中找出一點(diǎn)k使得uk={uj}。令p:=p∪

4、{k},T=T{k},若T=空集算法結(jié)束，并令di=ui(I=1,2,…n),否則進(jìn)入(3)；③（修改臨時(shí)標(biāo)號(hào)）對(duì)T中每一個(gè)點(diǎn)j，令uj=min{uj,uk+wij}，然后返回②。精品課程《運(yùn)籌學(xué)》例6.2.1求圖6-2-1中點(diǎn)v1到其它各點(diǎn)的最短路（弧旁的數(shù)字表示距離）。解用Dijkstra算法，這里只畫(huà)出每步所得圖得標(biāo)號(hào)的變化情況，即圖6-2-2，小方框內(nèi)數(shù)字即為各頂點(diǎn)到v1的最短路。寫出計(jì)算結(jié)果，具體步驟請(qǐng)讀者自己完成。精品課程《運(yùn)籌學(xué)》精品課程《運(yùn)籌學(xué)》2.最短路的矩陣算法（適用于所有權(quán)非

5、負(fù)的情況）最短路的矩陣算法是將圖表示成是矩陣形式，然后利用矩陣表計(jì)算出最短路。矩陣算法的原理與Dijkstra算法標(biāo)號(hào)算法完全相同，只是它采用了矩陣形式，顯得更為簡(jiǎn)潔，有利于計(jì)算機(jī)計(jì)算。下面先介紹圖的矩陣表示。精品課程《運(yùn)籌學(xué)》（1)圖的矩陣表示無(wú)權(quán)圖矩陣表示：兩頂點(diǎn)之間有邊相連的記為“1”，無(wú)邊相連的記為“0”，對(duì)角線上記為“0”。賦權(quán)無(wú)向圖矩陣表示：兩頂點(diǎn)之間有邊相連的，寫上它們的權(quán)數(shù)，無(wú)邊相連的記為“∞”，對(duì)角線上記為0。賦權(quán)有向圖的矩陣表示：左邊第一列為各條弧的起點(diǎn)。在每一行中，以該點(diǎn)為起點(diǎn)

6、，按弧的方向，依次填上到各點(diǎn)的權(quán)，若沒(méi)有到該點(diǎn)的弧，則權(quán)數(shù)為“∞”。精品課程《運(yùn)籌學(xué)》（2）最短路的矩陣算法最短路的矩陣算法步驟如下：①將圖表示成矩陣形式。②確定起點(diǎn)行，將其標(biāo)號(hào)確定為0，將相應(yīng)的列在矩陣表中劃去。③在已標(biāo)號(hào)的行中未劃去的元素中，找出最小元素aij,把它圈起來(lái)，此時(shí)把第j列劃去，同時(shí)給第j行標(biāo)號(hào)aij，并把第j行中未劃去的各元素都加上aij。這標(biāo)號(hào)的含義同標(biāo)號(hào)算法。精品課程《運(yùn)籌學(xué)》若還存在某些行未標(biāo)號(hào)，則返回③。如果各行均已獲得標(biāo)號(hào)（或終點(diǎn)行已獲得標(biāo)號(hào)），則終止計(jì)算。并利用倒向追蹤

7、，求得自起點(diǎn)到各點(diǎn)的最短通路。3．Ford算法(適用于含負(fù)權(quán)弧的情況)設(shè)D=(V，A，w)為有負(fù)權(quán)弧的有向圖，不妨設(shè)圖D中任兩點(diǎn)從vi到vj均有弧聯(lián)結(jié)（若沒(méi)有可認(rèn)為(vi，vj)存在且wij=+∞）且設(shè)D中只有n（n為常數(shù)）個(gè)點(diǎn)。精品課程《運(yùn)籌學(xué)》則d(j)可由以下迭代關(guān)系d(1)(j)=w1j(j=1,2,…,n)與d(k)(j)={d(i)+wij}(k=2,3,…)求出。若迭代到某一步k時(shí)，有d(k)(j)=d(k-1)(j)(j=1,2,3,…n)則運(yùn)算結(jié)束，且d(j)=d(k)(j)(j=

8、1,2,3,…n)精品課程《運(yùn)籌學(xué)》