資源描述：
《《短路問題》ppt課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第二節(jié)最短路問題§2.1基本概念與基本定理§2.2最短路的算法精品課程《運籌學(xué)》第二節(jié)最短路問題最短路問題是重要的最優(yōu)化問題之一，它不僅可以直接應(yīng)用于解決生產(chǎn)實際的許多問題，如管道鋪設(shè)、線路選擇，設(shè)備更新、投資等問題，而且經(jīng)常被作為一個基本工具，用于解決其它的優(yōu)化問題。精品課程《運籌學(xué)》§2.1基本概念與基本定理在有向圖G中，設(shè)P是有向圖D=（V，E）中從頂點u到v為點弧交替的序列。如果序列中每一條弧的始點和終點恰好分別是與它前后相鄰的頂點，則稱這個序列P是D中的一條路。精品課程《運籌學(xué)》設(shè)已給定了
2、一個有向賦權(quán)圖D=(V,A,w);wij≥0,((u,v)∈A)，若u是D中的一條路，則稱w(u)=∑wij為路u的總權(quán)數(shù)（或稱為路長）。設(shè)u,v是D=(V,A,w)中取定的兩個點，存在從u到v的路，稱從u到v的路中總權(quán)數(shù)最小者為最短路。對于最短路，顯然有下列定理成立.精品課程《運籌學(xué)》定理6.2.1有向圖D=(V,A,w)，V={1,2,..,n}，記dj為點1到點j的最短路的路長且不妨設(shè)當(dāng)1＜i＜j時有0＜di＜dj＜∞,則有d1=0及dj=min{di+wij}(j=1,2,…,n),其中wi
3、j為點i到點j的弧的權(quán)數(shù)。精品課程《運籌學(xué)》§2.2最短路的算法1．Dijkstra算法（適用于所有權(quán)非負(fù)的情況）Dijkstra算法是E.W.Dijkstra于1959年提出的，是目前公認(rèn)的對所有權(quán)非負(fù)的情況的最好算法。精品課程《運籌學(xué)》設(shè)D=(V,A,w)滿足上述定理條件，則有以下算法：①令u1=0,uj﹦wij(若不存在點1到點j的路則記w1j=∞),p={1},T={2,3,…,n}(p為以確定的點之集，T為未確定的點之集)；②（指出永久標(biāo)號）在T中找出一點k使得uk={uj}。令p:=p∪
4、{k},T=T{k},若T=空集算法結(jié)束，并令di=ui(I=1,2,…n),否則進(jìn)入(3)；③（修改臨時標(biāo)號）對T中每一個點j，令uj=min{uj,uk+wij}，然后返回②。精品課程《運籌學(xué)》例6.2.1求圖6-2-1中點v1到其它各點的最短路（弧旁的數(shù)字表示距離）。解用Dijkstra算法，這里只畫出每步所得圖得標(biāo)號的變化情況，即圖6-2-2，小方框內(nèi)數(shù)字即為各頂點到v1的最短路。寫出計算結(jié)果，具體步驟請讀者自己完成。精品課程《運籌學(xué)》精品課程《運籌學(xué)》2.最短路的矩陣算法（適用于所有權(quán)非
5、負(fù)的情況）最短路的矩陣算法是將圖表示成是矩陣形式，然后利用矩陣表計算出最短路。矩陣算法的原理與Dijkstra算法標(biāo)號算法完全相同，只是它采用了矩陣形式，顯得更為簡潔，有利于計算機(jī)計算。下面先介紹圖的矩陣表示。精品課程《運籌學(xué)》（1)圖的矩陣表示無權(quán)圖矩陣表示：兩頂點之間有邊相連的記為“1”，無邊相連的記為“0”，對角線上記為“0”。賦權(quán)無向圖矩陣表示：兩頂點之間有邊相連的，寫上它們的權(quán)數(shù)，無邊相連的記為“∞”，對角線上記為0。賦權(quán)有向圖的矩陣表示：左邊第一列為各條弧的起點。在每一行中，以該點為起點
6、，按弧的方向，依次填上到各點的權(quán)，若沒有到該點的弧，則權(quán)數(shù)為“∞”。精品課程《運籌學(xué)》（2）最短路的矩陣算法最短路的矩陣算法步驟如下：①將圖表示成矩陣形式。②確定起點行，將其標(biāo)號確定為0，將相應(yīng)的列在矩陣表中劃去。③在已標(biāo)號的行中未劃去的元素中，找出最小元素aij,把它圈起來，此時把第j列劃去，同時給第j行標(biāo)號aij，并把第j行中未劃去的各元素都加上aij。這標(biāo)號的含義同標(biāo)號算法。精品課程《運籌學(xué)》若還存在某些行未標(biāo)號，則返回③。如果各行均已獲得標(biāo)號（或終點行已獲得標(biāo)號），則終止計算。并利用倒向追蹤
7、，求得自起點到各點的最短通路。3．Ford算法(適用于含負(fù)權(quán)弧的情況)設(shè)D=(V，A，w)為有負(fù)權(quán)弧的有向圖，不妨設(shè)圖D中任兩點從vi到vj均有弧聯(lián)結(jié)（若沒有可認(rèn)為(vi，vj)存在且wij=+∞）且設(shè)D中只有n（n為常數(shù)）個點。精品課程《運籌學(xué)》則d(j)可由以下迭代關(guān)系d(1)(j)=w1j(j=1,2,…,n)與d(k)(j)={d(i)+wij}(k=2,3,…)求出。若迭代到某一步k時，有d(k)(j)=d(k-1)(j)(j=1,2,3,…n)則運算結(jié)束，且d(j)=d(k)(j)(j=
8、1,2,3,…n)精品課程《運籌學(xué)》
