用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(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)，圖論，運籌學等等。

　　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. 重復第2和第3步,直到OPEN表為空，或找到目標點。