最短路徑
最短路徑問題是圖論研究中的一個經(jīng)典算法問題， 旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。 算法具體的形式包括： 確定起點的最短路徑問題 - 即已知起始結(jié)點，求最短路徑的問題。 確定終點的最短路徑問題 - 與確定起點的問題相反，該問題是已知終結(jié)結(jié)點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題。 確定起點終點的最短路徑問題 - 即已知起點和終點，求兩結(jié)點之間的最短路徑。 全局最短路徑問題 - 求圖中所有的最短路徑。 編輯本段解決方法綜述
用于解決最短路徑問題的算法被稱做“最短路徑算法”， 有時被簡稱作“路徑算法”。 最常用的路徑算法有： Dijkstra算法 A*算法 SPFA算法 Bellman-Ford算法 Floyd-Warshall算法 Johnson算法 所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結(jié)點S∈V到V中的每個結(jié)點的最短路徑。 首先，我們可以發(fā)現(xiàn)有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那么，從vs沿P到vi的路是從vs到vi的最短路。 Dijkstra算法 Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。 Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 算法和 D* 算法表述一致，這里均采用OPEN,CLOSE表的方式。 其采用的是貪心法的算法策略 大概過程：
創(chuàng)建兩個表，OPEN, CLOSE。 OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。 1． 訪問路網(wǎng)中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。 2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節(jié)點，把這個點放到CLOSE表中。 3． 遍歷考察這個點的子節(jié)點。求出這些子節(jié)點距起始點的距離值，放子節(jié)點到OPEN表中。 4． 重復(fù)第2和第3步,直到OPEN表為空，或找到目標點。
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
