Dijkstra 算法

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

BFS 彈出: 層級(jí)最淺的原則，隊(duì)列里最下方的元素

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

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

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

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

Dijkstra 算法 偽代碼流程

維護(hù)一個(gè)優(yōu)先級(jí)隊(duì)列，存儲(chǔ)所有被擴(kuò)展的節(jié)點(diǎn)，且節(jié)點(diǎn)按g()值的大小自動(dòng)按從小到大排列。

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

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

-循環(huán)：

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

    2、彈出優(yōu)先級(jí)隊(duì)列中代價(jià)最小的節(jié)點(diǎn)n

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

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

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

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

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

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

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

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

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

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

Dijkstra 算法步驟示例

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

1、首先初始化隊(duì)列，將起始節(jié)點(diǎn)放入優(yōu)先級(jí)隊(duì)列中

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

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

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

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

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

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

也就是p節(jié)點(diǎn)

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

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

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

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

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

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