Dijkstra 算法

Dijkstra 算法與BFS算法的區(qū)別就是 : 從容器中彈出接下來要訪問的節(jié)點的規(guī)則不同

BFS 彈出: 層級最淺的原則，隊列里最下方的元素

Dijkstra 彈出: 代價最小的節(jié)點g(n)

g(n) :表示的是從開始節(jié)點到當(dāng)前n節(jié)點的代價累加

Dijkstra在擴(kuò)展的時候，同時考慮從n節(jié)點擴(kuò)展所有可擴(kuò)展節(jié)點的代價g()，如果某個節(jié)點m的代價g(m)比g(n)要小，則更新當(dāng)前代價為g(m)

Dijkstra的最優(yōu)性保證：圖運行的過程中，任何一個被擴(kuò)展或者訪問的節(jié)點，保證存儲的代價g()值是從起點節(jié)點開始到當(dāng)前節(jié)點的最小值

Dijkstra 算法 偽代碼流程

維護(hù)一個優(yōu)先級隊列，存儲所有被擴(kuò)展的節(jié)點，且節(jié)點按g()值的大小自動按從小到大排列。

-優(yōu)先級隊列首先為空，以起始節(jié)點Xs進(jìn)行初始化

-起始節(jié)點g(Xs)=0，并且初始化其它節(jié)點的代價為無窮大

-循環(huán)：

    1、如果隊列是空的，返回false，跳出循環(huán)

    2、彈出優(yōu)先級隊列中代價最小的節(jié)點n

    3、標(biāo)記節(jié)點n為被擴(kuò)展節(jié)點

    4、如果節(jié)點n為目標(biāo)節(jié)點，返回true,跳出循環(huán)

    5、找到n節(jié)點周圍可以擴(kuò)展的所以節(jié)點（沒被擴(kuò)展過）m

        6、進(jìn)行判斷 如果g(m)為無窮大（說明其它節(jié)點也沒發(fā)現(xiàn)過m）,

            7、則計算 真正的g(m)=g(n)+Cnm，然后將m節(jié)點加入到優(yōu)先級隊列中

        8、進(jìn)行判斷 如果g(m)不為無窮大，有值了(說明其它節(jié)點發(fā)現(xiàn)過m，m已經(jīng)在優(yōu)先級隊列中)

            9、再次進(jìn)行判斷 如果之前發(fā)現(xiàn)m時計算的g(m)比g(n)+Cnm大的話

                10、更新g(m)=g(n)+Cnm。

    11、重復(fù)循環(huán)至步驟1

-結(jié)束循環(huán)

Dijkstra 算法步驟示例

以這個圖將Dijkstra 算法運行的步驟進(jìn)行一個示例：

1、首先初始化隊列，將起始節(jié)點放入優(yōu)先級隊列中

2、彈出起始節(jié)點

3、擴(kuò)展彈出節(jié)點周圍的節(jié)點

起始節(jié)點S可以擴(kuò)展到子節(jié)點d\e\p，并且計算各節(jié)點的g值

4、將擴(kuò)展的節(jié)點加入到優(yōu)先級隊列中，并且進(jìn)行排序

g(p)最小，放到隊列最前面，也就是圖中的最下面，然后是d,最后是e。

5、彈出最小的g值節(jié)點

也就是p節(jié)點

然后循環(huán)至步驟3，直至結(jié)束

Dijkstra算法的優(yōu)劣分析

•優(yōu)點：完備的（如果問題有解，一定能找到解）；最優(yōu)的（找到的解一定是最優(yōu)的）

•缺點：沒有目標(biāo)終點方向的，只是比廣度搜索多了一個代價值判斷，如果每個邊的代價都是1的話，那么就變成了廣度搜索。

針對該缺點，與之對應(yīng)的就是啟發(fā)式搜索，例如貪心算法，根據(jù)到目標(biāo)的進(jìn)行一個啟發(fā)式搜索。

如果Dijkstra的最優(yōu)性與啟發(fā)式搜索結(jié)合，使搜索具有方向性時，也就是 A*算法了。