a演算法dijkstra

⑴ 最短路徑問題5種類型

最短路徑問題5種類型有Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，

擴展知識：

用於解決最短路徑問題的演算法被稱做「最短路徑演算法」，有時被簡稱作「路徑演算法」。最常用的路徑演算法有：
Dijkstra演算法、A*演算法、SPFA演算法、Bellman-Ford演算法和Floyd-Warshall演算法，本文主要介紹其中的三種。
最短路徑問題是圖論研究中的一個經典演算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
演算法具體的形式包括：確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。
確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同於把所有路徑方向反轉的確定起點的問題。
確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

⑵ 圖遍歷演算法之最短路徑Dijkstra演算法

最短路徑問題是圖論研究中一個經典演算法問題，旨在尋找圖中兩節點或單個節點到其他節點之間的最短路徑。根據問題的不同，演算法的具體形式包括：

常用的最短路徑演算法包括：Dijkstra演算法，A 演算法，Bellman-Ford演算法，SPFA演算法（Bellman-Ford演算法的改進版本），Floyd-Warshall演算法，Johnson演算法以及Bi-direction BFS演算法。本文將重點介紹Dijkstra演算法的原理以及實現。

Dijkstra演算法，翻譯作戴克斯特拉演算法或迪傑斯特拉演算法，於1956年由荷蘭計算機科學家艾茲赫爾.戴克斯特拉提出，用於解決賦權有向圖的 單源最短路徑問題 。所謂單源最短路徑問題是指確定起點，尋找該節點到圖中任意節點的最短路徑，演算法可用於尋找兩個城市中的最短路徑或是解決著名的旅行商問題。

問題描述 ：在無向圖 中， 為圖節點的集合， 為節點之間連線邊的集合。假設每條邊 的權重為 ，找到由頂點 到其餘各個節點的最短路徑（單源最短路徑）。

為帶權無向圖，圖中頂點 分為兩組，第一組為已求出最短路徑的頂點集合（用 表示）。初始時 只有源點，當求得一條最短路徑時，便將新增頂點添加進 ，直到所有頂點加入 中，演算法結束。第二組為未確定最短路徑頂點集合（用 表示），隨著 中頂點增加， 中頂點逐漸減少。

以下圖為例，對Dijkstra演算法的工作流程進行演示（以頂點 為起點）：

註：
01） 是已計算出最短路徑的頂點集合；
02） 是未計算出最短路徑的頂點集合；
03） 表示頂點 到頂點 的最短距離為3
第1步 ：選取頂點 添加進

第2步 ：選取頂點 添加進 ，更新 中頂點最短距離

第3步 ：選取頂點 添加進 ，更新 中頂點最短距離

第4步 ：選取頂點 添加進 ，更新 中頂點最短距離

第5步 ：選取頂點 添加進 ，更新 中頂點最短距離

第6步 ：選取頂點 添加進 ，更新 中頂點最短距離

第7步 ：選取頂點 添加進 ，更新 中頂點最短距離

示例：node編號1-7分別代表A,B,C,D,E,F,G

(s.paths <- shortest.paths(g, algorithm = "dijkstra"))輸出結果：

(s.paths <- shortest.paths(g,4, algorithm = "dijkstra"))輸出結果：

示例：

找到D（4）到G（7）的最短路徑：

[1] 維基網路，最短路徑問題： https://zh.wikipedia.org/wiki/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98 ；
[2]CSDN，Dijkstra演算法原理： https://blog.csdn.net/yalishadaa/article/details/55827681 ;
[3]RDocumentation: https://www.rdocumentation.org/packages/RNeo4j/versions/1.6.4/topics/dijkstra ;
[4]RDocumentation: https://www.rdocumentation.org/packages/igraph/versions/0.1.1/topics/shortest.paths ;
[5]Pypi: https://pypi.org/project/Dijkstar/

⑶ A*演算法優化

A演算法是游戲中路徑搜索的常見演算法。Dijkstra是最短路徑的經典演算法，A演算法的思路基本上和Dijkstra演算法一致，在Dijkstra演算法的基礎上增加了啟發函數，也就是：

f(n) = g(n) + h(n)

其中，n是路徑上某一點，g(n)是從出發點到該點的cost，h(n)是關於該點的啟發函數，通常是對從該點到目標花費的一個估計，例如到目標的直線距離或者曼哈頓距離。 A演算法每次選擇f(n)最小的點，然後更新所有g(n)。
如果你明白Dijkstra演算法，那麼在這里h(n) = 0 的話，A演算法就和Dijkstra演算法一樣了。
本文不詳細講解A演算法，需要詳細了解A演算法的具體過程的，參見以下兩篇文章：

理解A*演算法的具體過程
A*演算法詳解

A*演算法優化的關鍵在於h(n)的選擇。 一個啟發函數h(n)被稱為admissible的，是指h(n)的估計，不會超過節點N到目標的實際花費。
如果h(x)滿足以下條件，h(x)被稱為單調的(monotone, or consistent)。 對於任意一條邊(x,y),
h(x) <= d(x,y) + h(y)
其中d(x,y)是（x,y）的長度

如果滿足這個條件，就意味著沒有任何節點需要被處理多次，也就是說，在Dijkstra演算法中，新加入一個節點會導致已添加節點中cost降低的情況不會存在，也就不需要去更新已添加節點(稱為close set)。

如果一個啟發函數是單調的，那麼該啟發函數一定是admissible的。如果該啟發函數是admissible的，那麼可以證明A*在同類演算法中搜尋到最短的路徑。

問題出在這里：如果我們更在意的是搜索的時間空間花費，而不是最優結果，那麼A*演算法就有優化空間。所以我們放鬆要求，修改我們的啟發函數，使得我們搜尋到的路徑不會比最佳路徑差太多，就是優化演算法，稱為ε-admissible演算法。

有多種ε-admissible演算法，在此只舉例最簡單直接的一種： 加權A*(靜態加權)演算法。

假如ha(n)是一個admissible的啟發函數，我們選取新的啟發函數hw(n) = ε ha(n)，其中ε>1 作為啟發函數。就可以在某種程度上進行優化。 下圖1是使用ha(n)作為啟發式演算法，下圖2是使用hw(n)作為啟發式演算法，其中ε取5.

圖1：ha(x)作為啟發演算法

圖2：hn(x)作為啟發演算法

可以看出，ha(n)可以找到最小路徑，但是多了許多無用的搜索；而hw(n)找到的不是最優路徑，但是減少了大量無用搜索。
其他的優化演算法思路類似都是在於啟發函數的選擇。詳見參考文獻。

參考文獻：
https://en.wikipedia.org/wiki/A*_search_algorithm#Admissibility_and_optimality https://en.wikipedia.org/wiki/Consistent_heuristic

⑷ A*演算法 和 最佳優先搜索演算法（Best-First-Search）

最佳優先搜索演算法是一種啟發式搜索演算法（Heuristic Algorithm），其基於廣度優先搜索演算法，不同點是其依賴於估價函數對將要遍歷的節點進行估價，選擇代價小的節點進行遍歷，直到找到目標點為止。 BFS演算法不能保證找到的路徑是一條最短路徑，但是其計算過程相對於Dijkstra
演算法會快很多 。

最佳優先搜索是一種啟發式搜索演算法。廣度優先搜索和深度優先搜索都屬於窮舉類型的搜索，需要依次遍歷所有的節點，當空間非常大的時候，這種方式的效率就會非常差。而啟發式的搜索是對狀態控制項中的每個點進行評估，然後選出最好的位置。

啟發估價函數公式為：

n表示當前的點，g(n)為從起始點到點n的實際代價，h(n)為從點n到目標點的估價。

（圖片來源於網路）

A*演算法將BFS演算法和Dijkstra演算法結合在一起，結合兩演算法的優點，既可以查找最短路徑的，有擁有和BFS差不多的效率。

（圖片來源於網路）

A*演算法詳解

模擬尋路的地址

⑸ a*演算法求最短路徑和floyd還有dijsktra演算法求最短路徑的區別

A*演算法是啟發式搜索，適合點對點的最短路徑，單源單匯的情況
Floyd是動態規劃的一種，可以求出任意兩點之間的最短路徑
Dijkstra是貪婪演算法的一種，求一點到其他所有點的最短路，即所謂的單源最短路演算法
從時間復雜度來說
Floyd是O(N^3)
Dijkstra是O(N^2)
而啟發式搜索就不好說了……
結果當然是一樣的，都是最短路，但是適用情形和時空開銷就不同了
舉例來說，你做任意兩點間最短路可以用N次Dijkstra或者1次Floyd，時間消耗一樣，顯然用後者，而如果你只用求兩點間的，用Floyd就不合算了

⑹ 最短路徑演算法（Dijkstra）

Dijkstra（ 迪科斯特拉 ）演算法是用來解決單源最短路徑的演算法，要求路徑權值非負數。該演算法利用了深度優先搜索和貪心的演算法。

下面是一個有權圖，求從A到各個節點的最短路徑。

第1步：從A點出發，判斷每個點到A點的路徑（如果該點不能直連A點則距離值為無窮大，如果該點能和A直連則是當前的權值），計算完之後把A點上色，結果如下圖:

第2步：從除A點之外的點查找到距離A點最近的點C，從C點出發查找其鄰近的節點（除去已上色的點），並重新計算C點的鄰近點距離A點的值，如圖中B點，若新值（C點到A點的值+C點到該點的路徑）小於原值，則將值更新為5，同理更新D、E點。同時將C標記為已經處理過，如圖所示塗色。

第3步：從上色的節點中查找距離A最近的B點，重復第3步操作。

第4步： 重復第3步，2步，直到所有的節點都上色。

最後就算出了從A點到所有點的最短距離。

leetcode 743題

⑺ A*演算法（啟發式演算法）

A*演算法
這是我寫的第一篇有關A*演算法的文章，寫得比較簡潔，我決定再寫一篇，補充一下對A*演算法的理解。

A*演算法把 Dijkstra演算法 （靠近初始點的結點）和 BFS演算法 （靠近目標點的結點）的信息塊結合起來。
g(n)表示從初始結點到任意結點n的實際代價
h(n)表示從結點n到目標點的啟發式評估代價

（1）h(n)=0，一種極端情況
如果h(n)=0，則只有g(n)起作用，此時A*演變成Dijkstra演算法，這保證能找到最短路徑，但效率不到，因為得不到啟發。
（2）h(n)<實際代價
如果h(n)經常都比從n移動到目標的實際代價小（或者相等），則A*保證能找到一條最短路徑。h(n)越小，A*擴展的結點越多，運行就越慢。
（3）h(n)=實際代價
如果h(n)精確地等於從n移動到目標的實際代價，則A*將會僅僅尋找最佳路徑而不擴展別的任何結點，這會運行得非常快。盡管這不可能在所有情況下發生，你仍可以在一些特殊情況下讓它們精確地相等（指讓h(n)精確地等於實際代價）。只要提供完美的信息，A*就會運行得很完美。
（4）h(n)>實際代價
如果h(n)有時比從n移動到目標的實際代價大，則A*不能保證找到一條最短路徑，但它運行得更快。
（5）h(n)>>實際代價（>>遠大於），另一種極端情況
如果h(n)比g(n)大很多，則只有h(n)起作用，A*演變成BFS演算法。

數組？鏈表？
在Open集上主要有三種操作：查找優先順序最高的結點&刪除結點、查找相鄰結點是否在集合中、插入新結點
在Close集上主要有兩種操作：查找相鄰結點是否在集合中、插入新節點
（1）未排序數組或鏈表
最簡單的數據結構是未排序數組或鏈表。查找結點，花費O(N)；插入結點，花費O(1)；刪除結點，花費O(N)
（2）排序數組
為了加快刪除操作，可以對數組進行排序。查找結點，變成O(logN)，因為可以使用折半查找；插入結點，花費O(N)；查找和刪除優先順序最高的結點，花費O(1)
（3）排序鏈表
在排序數組中，插入操作很慢。如果使用鏈表則可以加速該操作。查找結點，花費O(N)；插入結點，花費O(1)，但查找插入位置，需要花費O(N)
（4）哈希表
使用哈希表，查找結點，花費O(1)；插入結點，花費O(1)；查找和刪除優先順序最高的結點，花費O(N)

https://blog.csdn.net/coutamg/article/details/53923717#!/_alzvzu0wsphb4nstr5bbro1or