最短路徑是什麼

　　用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充套件，直到擴充套件到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。
       解決方法

　　綜述

　　用於解決最短路徑問題的演算法被稱做“最短路徑演算法”， 有時被簡稱作“路徑演算法”。 最常用的路徑演算法有：

　　Dijkstra演算法

　　A*演算法

　　SPFA演算法

　　Bellman-Ford演算法

　　Floyd-Warshall演算法

　　Johnson演算法

　　所謂單源最短路徑問題是指：已知圖G=***V，E***，我們希望找出從某給定的源結點S∈V到V中的每個結點的最短路徑。

　　首先，我們可以發現有這樣一個事實：如果P是G中從vs到vj的最短路，vi是P中的一個點，那麼，從vs沿P到vi的路是從vs到vi的最短路。

　　Dijkstra演算法

　　Dijkstra***迪傑斯特拉***演算法是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充套件，直到擴充套件到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

　　Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如資料結構，圖論，運籌學等等。

　　Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這裡均採用OPEN,CLOSE表的方式。

　　其採用的是貪心法的演算法策略

　　大概過程：

　　建立兩個表，OPEN, CLOSE。

　　OPEN表儲存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。

　　1. 訪問路網中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。

　　2. 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。

　　3. 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。

　　4. 重複第2和第3步,直到OPEN表為空，或找到目標點。