本系列為筆者初學(xué)c/c++和游戲AI開(kāi)發(fā)的學(xué)習(xí)過(guò)程，算法為主，不涉及到具體的游戲開(kāi)發(fā)軟件學(xué)習(xí)(如unity，虛幻4等),若有錯(cuò)誤請(qǐng)?jiān)谠u(píng)論區(qū)留下批評(píng)意見(jiàn)。? ???

• 語(yǔ)言：c/c++ (11及以上)

• 平臺(tái)：macOS mojave

• 編輯器/編譯器：vs Code / g++

圖與路徑查找

五、Dijkstra算法

5.1 介紹

??迪杰斯特拉算法（音譯）是荷蘭計(jì)算機(jī)科學(xué)家艾茲赫爾·戴克斯特拉在1956年發(fā)現(xiàn)的算法，并于3年后在期刊上發(fā)表。

? 該算法使用盲目搜索方法和貪心思想來(lái)解決賦權(quán)圖的單源最短路徑問(wèn)題。

? 簡(jiǎn)單來(lái)講可以概括為，從A點(diǎn)到B點(diǎn)，每次從當(dāng)前點(diǎn)周?chē)丛L問(wèn)過(guò)的節(jié)點(diǎn)中選取路徑最短的那個(gè)點(diǎn)，加入路徑。

? 可以將其視作是BFS算法的一個(gè)改良，在盲目搜索的基礎(chǔ)上，增加了一個(gè)距離計(jì)算來(lái)減少搜索的計(jì)算量。

? 筆者這里就不多啰嗦的介紹該算法的證明過(guò)程，感興趣的讀者可以直接閱讀論文或者到維基百科上去查閱。

http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf? ? ? ? 論文地址

5.2 算法描述

??初始時(shí)，原點(diǎn)s的路徑權(quán)重被賦為 0 （d[s]=0, 即原點(diǎn)的實(shí)際最短路徑=0)。同時(shí)把所有其他頂點(diǎn)的路徑長(zhǎng)度設(shè)為無(wú)窮大，即表示我們不知道任何通向這些頂點(diǎn)的路徑?。

? 算法維護(hù)兩個(gè)頂點(diǎn)集合S和Q，集合S保留所有已知實(shí)際最短路徑值的頂點(diǎn)（已訪問(wèn)過(guò)），而集合Q則保留其他所有未訪問(wèn)過(guò)的頂點(diǎn)。

? 集合S初始狀態(tài)為空，之后每一步，從Q中選取一個(gè)頂點(diǎn)u放入S，該頂點(diǎn)u是d[u]最小的點(diǎn)（從起始點(diǎn)s到頂點(diǎn)u的最短距離）；然后，對(duì)u的每條外接邊w(u, v)進(jìn)行松弛操作(即u的鄰接頂點(diǎn)v，w是u到v的距離)。

? 松弛操作：如果存在一條從u到v的邊，且 d[u] + w(u, v) < d[v]，則令 d[v] =?d[u] + w(u, v)。

? 當(dāng)算法結(jié)束時(shí)，d[v] 中存儲(chǔ)的是從s到v的最短路徑，如果路徑不存在的話是無(wú)窮大。

5.3?偽代碼

5.3?Dijkstra算法 與 A*算法

? 如果讀者有心的話，可以發(fā)現(xiàn)，A*算法其實(shí)也是Dijkstra算法的進(jìn)一步改良。

? A*算法在判斷前向最短距離的同時(shí)，也判斷到目標(biāo)節(jié)點(diǎn)的最短距離，同時(shí)計(jì)算兩個(gè)方向的最短路徑，這樣可以排除掉大量不符合條件的節(jié)點(diǎn)。

? 在啟發(fā)函數(shù) F = G + H中，如果令H=0，即只求G值，那A*算法將轉(zhuǎn)化為單源最短路徑問(wèn)題，即Dijkstra算法。

? 我們用實(shí)驗(yàn)來(lái)觀察這個(gè)現(xiàn)象：

? 從上圖可以很明顯的看出，同樣的從A點(diǎn)到B點(diǎn)，A*算法的搜索路徑要小的非常多（綠色部分），并且也能找到一條短路徑。

? 在圖上，水平或垂直移動(dòng)一格距離為10，斜角距離為14，所以：

A*Path = 14 + 10 + 10 + 14 = 48

DijkstraPath = 10?+ 10?+14 +14 =?48

? 可見(jiàn)，雖然最終的查找路徑不同，但均是一個(gè)最短路徑解，且前者的計(jì)算量要遠(yuǎn)少得多。

5.4?Dijkstra算法代碼實(shí)現(xiàn)

? 代碼實(shí)現(xiàn)其實(shí)只要在BFS的基礎(chǔ)上加入松弛操作就可以。

? 但有個(gè)地方需要特別注意，由于筆者使用智能指針來(lái)保存查找路徑，且在getSurroundPoints方法中每次都是返回新建的指針，因此若一個(gè)節(jié)點(diǎn)存在需要多次更新d[v]的情況，則會(huì)發(fā)生數(shù)組中存在多個(gè)該節(jié)點(diǎn)的指針版本的情況。

? 這種情況下，雖然還是能的到準(zhǔn)確的最短路徑長(zhǎng)度，但當(dāng)我們需要返回這個(gè)節(jié)點(diǎn)指針來(lái)渲染到地圖上的時(shí)候，這些節(jié)點(diǎn)還是會(huì)指向舊指針，而不會(huì)更新。

? 所以我們需要額外判斷該節(jié)點(diǎn)是否已經(jīng)有舊指針存在，若有的話直接在這個(gè)舊指針上進(jìn)行更新。

?參考?

• 維基百科

• 相關(guān)代碼下載? ??https://github.com/linpeijie/GameToy