通信網(wǎng)基礎(chǔ)5.2最短路徑算法

1、路由:最短路徑算法 北京交通大學(xué)電信學(xué)院2015-3-25通信網(wǎng)理論基礎(chǔ)(10L534Q)2內(nèi)容路由概述圖論基礎(chǔ)最小重量生成樹(shù)最短路由算法問(wèn)題和措施互聯(lián)網(wǎng)路由回顧：路由和路由表數(shù)據(jù)層面: 使用路由表轉(zhuǎn)發(fā)分組控制層面: 建立和維護(hù)路由表 使用距離向量協(xié)議、鏈路狀態(tài)協(xié)議)H1H2R1R2R3R4R5R6H2 R4H2 R6Fwd tableFwd table引言有向圖/無(wú)向圖路由即路徑；路徑是沒(méi)有環(huán)的行走(Walk)從節(jié)點(diǎn)1到節(jié)點(diǎn)11，有24條路徑如何找出其中的最短路？6如何計(jì)算最短路徑經(jīng)典算法Bellman-Ford算法Dijkstra算法實(shí)現(xiàn)方式集中式分布式Bellman-Ford 算法B-F

2、算法，離向量算法目的：給定一個(gè)網(wǎng)絡(luò)拓?fù)?，每個(gè)節(jié)點(diǎn)v都要找到從任意節(jié)點(diǎn)s到其自己的最短路徑基本思想：我不知道怎么走，我可以問(wèn)問(wèn)我身邊的人，怎么走；每個(gè)節(jié)點(diǎn)v都盤算，自己的每個(gè)鄰居節(jié)點(diǎn)u到s有多遠(yuǎn)，看看從哪個(gè)u走，距離s最近。每個(gè)節(jié)點(diǎn)v按下面的算法計(jì)算最短路關(guān)鍵算法v120.52.150.1d(v) = 2.6s 到 v的最短路徑長(zhǎng)度 w(u,v): Node u 到v 的權(quán)重S完整算法還應(yīng)考慮什么？初始化 源節(jié)點(diǎn) d0(s) = 0,初始化 其他節(jié)點(diǎn) d0(v) = 3. 如果有任何節(jié)點(diǎn)，dt-1(v)dt(v) 對(duì)鏈路數(shù)進(jìn)行迭代完整的 B-F 算法注意寫法初始化59678-32sabcd0-2

3、7-4Edgeorder(a,b)(a,c)(a,d)(b,a)(c,b)(c,d)(d,s)(d,b)(s,a)(s,b)59678-32sabcd067-27-4Edgeorder(a,b)(a,c)(a,d)(b,a)(c,b)(c,d)(d,s)(d,b)(s,a)(s,c)迭代一次59678-32sabcd06472-27-4Edgeorder(a,b)(a,c)(a,d)(b,a)(c,b)(c,d)(d,s)(d,b)(s,a)(s,c)11迭代二次59678-32sabcd02472-27-4Edgeorder(a,b)(a,c)(a,d)(b,a)(c,b)(c,d)(d,s

4、)(d,b)(s,a)(s,b)6迭代三次59678-32sabcd0247-2-27-4Edgeorder(a,b)(a,c)(a,d)(b,a)(c,b)(c,d)(d,s)(d,b)(s,a)(s,b)2迭代四次B-F復(fù)雜度對(duì)每個(gè)v，每次迭代過(guò)程循環(huán)N-1次；每次迭代要對(duì)每個(gè)節(jié)點(diǎn)v計(jì)算一遍，共N-1次計(jì)算；一共要執(zhí)行至少N-1步大循環(huán)，結(jié)果才能穩(wěn)定下來(lái)；因此：復(fù)雜度O(N3)實(shí)現(xiàn)方式集中式分布式分布式B-F算法基本思想各個(gè)節(jié)點(diǎn)v獨(dú)立運(yùn)行，不掌握全網(wǎng)拓?fù)湫畔?；只好向鄰居們u打探是否可借道通往源點(diǎn)s ；節(jié)點(diǎn)v根據(jù)鄰居u的反饋，計(jì)算出B-F最短路徑優(yōu)點(diǎn)：適應(yīng)網(wǎng)絡(luò)和條件的動(dòng)態(tài)變化如流量波動(dòng)、鏈路

5、故障缺點(diǎn)是分布式B-F算法對(duì)任意節(jié)點(diǎn)i，具體步驟i 不斷測(cè)量自己到其鄰居 j 的距離dij；i 接收并記錄 j 發(fā)來(lái)的路由表Dj，其中列出了j到達(dá)各節(jié)點(diǎn)的最短距離；i 根據(jù)Dj和dij更新Di，并將Di發(fā)送給它的所有鄰居例J收到的鄰居的路由表B-F算法小結(jié)每個(gè)節(jié)點(diǎn)只向鄰居發(fā)送路由信息路由信息幾乎就是整張路由表路由信息只包括到達(dá)目的的長(zhǎng)度值，不包括具體怎么走路由環(huán)、收斂問(wèn)題！下一小節(jié)：Dijkstra算法21Dijkstra 算法目的：計(jì)算圖中某源點(diǎn)s到其它各個(gè)點(diǎn)的最短路徑出發(fā)點(diǎn)：與B-F不同，如果每個(gè)節(jié)點(diǎn)都掌握全網(wǎng)真實(shí)的拓?fù)湫畔?，?yīng)該能有收斂性更好的路由算法基本思想鄰居轉(zhuǎn)告我的信息不能全信，我

6、要親自找不依賴別人告知的路由，根據(jù)網(wǎng)絡(luò)拓?fù)?，逐個(gè)找到去向每個(gè)節(jié)點(diǎn)的最短路徑問(wèn)題：怎么才能獲得全網(wǎng)信息？Dijkstra 算法0suvyx105123946721050suvyx10512394672基于路徑長(zhǎng)度的迭代/初始化 1 N = s 2 for all nodes v 3 如果 v 與 s直接相鄰 4 then D(v) = d(s,v) 5 else D(v) = infinity /迭代過(guò)程6 Loop7 找到 minD(i), iN8 N N + i 9 刷新所有D(j)，jN D(j) min D(j), D(l) + d(l,j ) 10 until all nodes in

7、 N uv814570syx10512394672813570suvyx10512394672Dijkstra 算法基于路徑長(zhǎng)度的迭代/初始化 1 N = s 2 for all nodes v 3 如果 v 與 s直接相鄰 4 then D(v) = d(s,v) 5 else D(v) = infinity /迭代過(guò)程6 Loop7 找到 minD(i), iN8 N N + i 9 刷新所有D(j)，jN D(j) min D(j), D(l) + d(l,j ) 10 until all nodes in N 89570uvyx10512394672基于路徑長(zhǎng)度的迭代Dijkstra 算法/初始化 1 N = s 2 for all nodes v 3 如果 v 與 s直接相鄰 4 then D(v) = d(s,v) 5 else D(v) = infinity /迭代過(guò)程6 Loop7 找到 minD(i), iN8 N N + i 9 刷新所有D(j)，jN D(j) min D(j), D(l) + d(l,j ) 10 until all nodes in N Dijkstra算法的實(shí)現(xiàn)集中式由一個(gè)節(jié)點(diǎn)收集到全網(wǎng)拓?fù)?，用Dijkstra算法計(jì)算路由；然后，將結(jié)果廣播到全網(wǎng)。分布式算法每個(gè)節(jié)點(diǎn)把鄰居關(guān)系(鏈路狀態(tài))向全網(wǎng)廣播，使每個(gè)節(jié)