OPSF之迪杰斯特拉算法ppt課件.ppt

《OPSF之迪杰斯特拉算法ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、——Dijkstra算法OSPF之最短路徑算法一、應(yīng)用背景（1）應(yīng)用背景——管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新、網(wǎng)絡(luò)拓?fù)涞?。?）現(xiàn)實(shí)生活中的網(wǎng)絡(luò)拓?fù)?，可以抽象成由?jié)點(diǎn)（路由器）和邊（路由器之間的鏈路）構(gòu)成的有向連通圖，鏈路的代價(jià)可以抽象成邊的權(quán)函數(shù)。之所以稱圖為有向圖，是因?yàn)橥粭l鏈路（邊）不同方向的權(quán)值可能不一樣?！皢卧醋疃搪窂健眴?wèn)題：已知一個(gè)有n個(gè)節(jié)點(diǎn)(V0..n)構(gòu)成的有向連通圖G＝（V，E），以及圖中邊的權(quán)函數(shù)C(E)，其中V代表節(jié)點(diǎn)集合，E表示所有邊的集合，并假設(shè)所有權(quán)非負(fù)，求由G中指定節(jié)點(diǎn)V0到其他各個(gè)節(jié)點(diǎn)的最短路徑。Dijkstra算法

2、是很經(jīng)典的求解上述問(wèn)題的算法，其基本想法是設(shè)計(jì)一種最短路徑樹的構(gòu)造方法，按非降次序逐條構(gòu)造從V0到各個(gè)節(jié)點(diǎn)的最短路徑.二、最短路算法1．D氏標(biāo)號(hào)法（Dijkstra）；邊權(quán)非負(fù)2.列表法（福德法）；有負(fù)權(quán)，無(wú)負(fù)回路4v1v2v3v4v6v5v7225614134121．D氏標(biāo)號(hào)法（Dijkstra）（1）求解思路——從始點(diǎn)出發(fā)，逐步順序地向外探尋，每向外延伸一步都要求是最短的。（2）使用條件——網(wǎng)絡(luò)中所有的弧權(quán)均非負(fù)，即。（3）選用符號(hào)的意義：①P標(biāo)號(hào)（Permanent固定/永久性標(biāo)號(hào)）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)②T標(biāo)號(hào)（Temporary臨時(shí)性標(biāo)號(hào)

3、）——從始點(diǎn)到該標(biāo)號(hào)點(diǎn)的最短路權(quán)上界（4）?計(jì)算步驟及例子：第一步：給起始點(diǎn)v1標(biāo)上固定標(biāo)號(hào),其余各點(diǎn)標(biāo)臨時(shí)性標(biāo)號(hào)T(vj)=?,j?1;=l1j第二步：考慮滿足如下條件的所有點(diǎn)①與v1相鄰的點(diǎn)，即;②具有T標(biāo)號(hào)，即，為T標(biāo)號(hào)點(diǎn)集.修改的T標(biāo)號(hào)為，并將結(jié)果仍記為T(vj)。svj?若網(wǎng)絡(luò)圖中已無(wú)滿足此條件的T標(biāo)號(hào)點(diǎn)，停止計(jì)算。第三步：令,然后將的T標(biāo)號(hào)改成P標(biāo)號(hào)，轉(zhuǎn)入第二步。此時(shí)，要注意將第二步中的改為。通俗易懂的步驟：(1)初始時(shí)，S只包含起點(diǎn)s；U包含除s外的其他頂點(diǎn)，且U中頂點(diǎn)的距離為"起點(diǎn)s到該頂點(diǎn)的距離"[例如，U中頂點(diǎn)v的距離為(s,v)的長(zhǎng)度

4、，然后s和v不相鄰，則v的距離為∞。(2)從U中選出"距離最短的頂點(diǎn)k"，并將頂點(diǎn)k加入到S中；同時(shí)，從U中移除頂點(diǎn)k。(3)更新U中各個(gè)頂點(diǎn)到起點(diǎn)s的距離。之所以更新U中頂點(diǎn)的距離，是由于上一步中確定了k是求出最短路徑的頂點(diǎn)，從而可以利用k來(lái)更新其它頂點(diǎn)的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。(4)重復(fù)步驟(2)和(3)，直到遍歷完所有頂點(diǎn)。237184566134105275934682求從1到8的最短路徑237184566134105275934682X={1}min{d12,d14,d16}=min{0+2,0+1,0+

5、3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{d12,d16,d42,d47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{d16,d23,d25,d47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=32371845661

6、34105275934682X={1,2,4,6}min{d23,d25,c47,d67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{d23,d25,d75,d78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682

7、X={1,2,4,6,7}min{d23,d53,d58,d78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134

8、105275934682X={1,2,3,4,6,7,8}1到8的