? ospf學(xué)習(xí)-----SPF最短路徑算法

轉(zhuǎn)載鏈接：https://blog.csdn.net/xu119718/article/details/68067891

姓名：羅學(xué)元學(xué)號：21181214375? ? 學(xué)院：廣州研究院

【嵌牛導(dǎo)讀】SPF最短路徑算法

【嵌牛鼻子】SPF最短路徑算法

【嵌牛提問】SPF最短路徑算法實現(xiàn)

常見的路由協(xié)議比如RIP、IGRP、BGP是距離矢量協(xié)議，OSPF和ISIS是數(shù)據(jù)鏈路狀態(tài)協(xié)議。矢量協(xié)議路由器只知道本身和與自身相連的接口路由信息，矢量圖只是一張方向圖，在路由傳播的過程中，容易造成環(huán)路。RIP路由器采用扁平化設(shè)計規(guī)避環(huán)路，BGP則采用As-path規(guī)避環(huán)路。OSPF是數(shù)據(jù)鏈路狀態(tài)路由協(xié)議，采用的SPF算法，即最小生成樹算法（Dijkstar），ospf內(nèi)不存在路由環(huán)路，但是OSPF間傳遞路由信息的時候，卻是矢量路由協(xié)議，也就是說OSPF之間傳遞路由信息的時候，會產(chǎn)生路由環(huán)路。

? ? ? Dijkstar 算法：

1、 算法目的：

在無向圖 G=(V,E) 中，假設(shè)每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其余各點的最短路徑。（單源最短路徑）

2、 算法描述：

算法思想：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。

3、算法步驟：

a.初始時，S只包含源點，即S＝{v}，v的距離為0。U包含除v外的其他頂點，即:U={其余頂點}，若v與U中頂點u有邊，則<u,v>正常有權(quán)值，若u不是v的出邊鄰接點，則<u,v>權(quán)值為∞。b.從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。c.以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。d.重復(fù)步驟b和c直到所有頂點都包含在S中。

4、算法實例：

用Dijkstra算法找出以A為起點的單源最短路徑步驟如下

即已A為根節(jié)點，對樹進行遍歷的結(jié)果：s=

<A、C、B、D、E、F>