- 论坛徽章:
- 0
|
Dijkstra's algorithm 关于最短路径的，大家帮帮我
附錄一 Dijkstra’s Algorithm
Dijkstra’s algorithm是用來找出一個圖形（graph）中某點到其它各點間最短路徑的演算法。OSPF用此演算法來找出各router之間的最短路徑。
利用Dijkstra’s algorithm想要求出圖形中某一點R到其它各點的最短路徑，其計算步驟如下：
（一）開始建立一最短路徑樹（Shortest Path Tree），以R當作此樹的根點（root），並將此樹根當作目前的處理點。
（二）加入目前處理點的所有相鄰點加到樹中，並且計算出由root到這些新加入點的距離。
（三）由目前已形成的樹中找出最短的一條路徑。若此路徑的最末端點為L，則此一路徑代表由R到L的最短路徑。所以刪除在路徑樹中其它末端為L的點，不必再找。
（四）以L當作目前的處理點，重覆步驟二、三、四。如果遇到已被找出的最短路徑的點就不必將此點再加入樹中。
以下我們用第二章中的網路架構為例（見上圖），router A中有一份Link State Database，內含每一個router到其相鄰router的距離（metric），如下表所示。
A
B
C
D
E
F
B 8
A 8
A 32
B 17
C 14
C 12
C 32
D 17
D 10
C 10
D 12
D 20
E 14
F 12
欲利用Dijkstra’s algorithm找出由router A到其它各router間的最短路徑，其步驟如下：
（一）以router A作為root，開始建立Shortest Path Tree。A到自已的距離為0。
（二）加入A的鄰居，B、C及D，並且利用Link State Database中的metric資料計算出由A到這些新加入點的距離，分別為8，32及20。
（三）目前三條路徑中最小的是AB，所以A若想透過C或D再經其它點到達B，所需距離鐵定大於AB的直接距離（「20加上某數」及「30加上某數」都一定大於8）。 所以AB是A到B的最短路徑。確定由A到B的最短路徑後，將B的鄰居D加入樹中，且計算出ABD的距離為8 + 17 = 25。
（四）目前的所有路徑中，以AD為最短，故可確定A到D之最短路徑為20，經其它路徑到D的距離為25加某數（ABD）或32加某數（AC），一定大於20。確定到D的最短路徑後，將D的鄰居（尚未求出最短距離的只有C和E）加入樹中，並刪去樹中另一為D的端點。
（五）目前的所有路徑中，以ADC為最短，故可確定A到C之最短路徑為30，確定到C的最短路徑後，將C的鄰居加入樹中，並刪去樹中另一為C的端點。
（六）目前的所有路徑中，以ADF為最短，故可確定A到F之最短路徑為32。確定到F的最短路徑後，因為F沒有尚未被找到最短路徑的鄰居，故不加入其它端點，但將樹中另一為F的端點刪除。
（七）最後，剩下一條ADCE的路徑，即為A到E的最短路徑，因為E沒有尚未被找到最短路徑的鄰居，故不用加入其它端點，計算過程到此終止。
（八）完成整個Shortest Path Tree。
參考資料
1、”Routing Information Protocol” ( rip.doc ) -- Charles Hedrick , Rutgers University.
2、”Designing Large - Scale IP Internetworks” -- Cisco IOSTM Software Documentation.
3、”OSPF Design Guide” – Cisco IOSTM Software Documentation.
4、RFC 791 “Internet Protocol - Protocol Specification” -- Editor : Jon Postel, Information Sciences Institute University of Southern California, September 1981.
上google查找会更多
如果只是想了解这个算法的话google得到的消息已够用了 |
|
免费注册
发表于 2003-05-21 15:30
