用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。
解決方法

　　綜述

　　用于解決最短路徑問題的算法被稱做“最短路徑算法”， 有時(shí)被簡稱作“路徑算法”。 最常用的路徑算法有：

　　Dijkstra算法

　　A*算法

　　SPFA算法

　　Bellman-Ford算法

　　Floyd-Warshall算法

　　Johnson算法

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

　　首先，我們可以發(fā)現(xiàn)有這樣一個(gè)事實(shí)：如果P是G中從vs到vj的最短路，vi是P中的一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。

　　Dijkstra算法

　　Dijkstra(迪杰斯特拉)算法是典型的最短路徑路由算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低。

　　Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。

　　Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 算法和 D* 算法表述一致，這里均采用OPEN,CLOSE表的方式。

　　其采用的是貪心法的算法策略

　　大概過程：

　　創(chuàng)建兩個(gè)表，OPEN, CLOSE。

　　OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。

　　1. 訪問路網(wǎng)中距離起始點(diǎn)最近且沒有被檢查過的點(diǎn)，把這個(gè)點(diǎn)放入OPEN組中等待檢查。

　　2. 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn)，把這個(gè)點(diǎn)放到CLOSE表中。

　　3. 遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到OPEN表中。

　　4. 重復(fù)第2和第3步,直到OPEN表為空，或找到目標(biāo)點(diǎn)。