Dijkstra's algorithm 關(guān)于最短路徑的，大家?guī)蛶臀?/a>

zephyr82

那位大俠給我講講Dijkstra's的最短路徑的算法啊~~~

好難啊~~


還有就是下面網(wǎng)頁(yè)里面是一個(gè)模擬最短路徑的Java的程序，我的機(jī)子怎么顯示不了里面的Java程序？  大家?guī)蛶臀?br />
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

無(wú)雙

附錄一　Dijkstra’s Algorithm
　　Dijkstra’s algorithm是用來(lái)找出一個(gè)圖形（graph）中某點(diǎn)到其它各點(diǎn)間最短路徑的演算法。OSPF用此演算法來(lái)找出各router之間的最短路徑。



　　利用Dijkstra’s algorithm想要求出圖形中某一點(diǎn)R到其它各點(diǎn)的最短路徑，其計(jì)算步驟如下：

�。ㄒ唬╅_始建立一最短路徑樹（Shortest Path Tree），以R當(dāng)作此樹的根點(diǎn)（root），並將此樹根當(dāng)作目前的處理點(diǎn)。

　（二）加入目前處理點(diǎn)的所有相鄰點(diǎn)加到樹中，並且計(jì)算出由root到這些新加入點(diǎn)的距離。

　（三）由目前已形成的樹中找出最短的一條路徑。若此路徑的最末端點(diǎn)為L(zhǎng)，則此一路徑代表由R到L的最短路徑。所以刪除在路徑樹中其它末端為L(zhǎng)的點(diǎn)，不必再找。

�。ㄋ模┮訪當(dāng)作目前的處理點(diǎn)，重覆步驟二、三、四。如果遇到已被找出的最短路徑的點(diǎn)就不必將此點(diǎn)再加入樹中。




　　以下我們用第二章中的網(wǎng)路架構(gòu)為例（見上圖），router A中有一份Link State Database，內(nèi)含每一個(gè)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間的最短路徑，其步驟如下：

�。ㄒ唬┮詒outer A作為root，開始建立Shortest Path Tree。A到自已的距離為0。






�。ǘ�）加入A的鄰居，B、C及D，並且利用Link State    Database中的metric資料計(jì)算出由A到這些新加入點(diǎn)的距離，分別為8，32及20。






�。ㄈ�）目前三條路徑中最小的是AB，所以A若想透過(guò)C或D再經(jīng)其它點(diǎn)到達(dá)B，所需距離鐵定大於AB的直接距離（「20加上某數(shù)」及「30加上某數(shù)」都一定大於8）。 所以AB是A到B的最短路徑。確定由A到B的最短路徑後，將B的鄰居D加入樹中，且計(jì)算出ABD的距離為8 + 17 = 25。






　（四）目前的所有路徑中，以AD為最短，故可確定A到D之最短路徑為20，經(jīng)其它路徑到D的距離為25加某數(shù)（ABD）或32加某數(shù)（AC），一定大於20。確定到D的最短路徑後，將D的鄰居（尚未求出最短距離的只有C和E）加入樹中，並刪去樹中另一為D的端點(diǎn)。






�。ㄎ澹┠壳暗乃�有路徑中，以ADC為最短，故可確定A到C之最短路徑為30，確定到C的最短路徑後，將C的鄰居加入樹中，並刪去樹中另一為C的端點(diǎn)。






　（六）目前的所有路徑中，以ADF為最短，故可確定A到F之最短路徑為32。確定到F的最短路徑後，因?yàn)镕沒有尚未被找到最短路徑的鄰居，故不加入其它端點(diǎn)，但將樹中另一為F的端點(diǎn)刪除。




�。ㄆ撸┳钺�，剩下一條ADCE的路徑，即為A到E的最短路徑，因?yàn)镋沒有尚未被找到最短路徑的鄰居，故不用加入其它端點(diǎn)，計(jì)算過(guò)程到此終止。




　（八）完成整個(gè)Shortest Path Tree。




參考資料


1、”Routing Information Protocol” ( rip.doc ) -- Charles Hedrick , Rutgers University.



2、”Designing Large - Scale IP Internetworks” -- Cisco IOSTM Software Documentation.



3、”O(jiān)SPF 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查找會(huì)更多
如果只是想了解這個(gè)算法的話google得到的消息已夠用了