Dijkstra's algorithm 關於最短路徑的，大家幫幫我 那位大俠給我講講Dijkstra's的最短路徑的算法啊~~~ 好難啊~~ :? 還有就是下面網頁裡面是一個模擬最短路徑的Java的程序，我的機子怎麼顯示不了裡面的Java程序？  大家幫幫我 http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html 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得到的消息已夠用了 [ 關閉窗口 ]