a最短路徑演算法

1. 最短路徑演算法（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題

2. 圖遍歷演算法之最短路徑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/

3. 最短路徑問題5種類型

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

擴展知識：

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

4. 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

5. 最短路徑演算法

Dijkstra演算法，A*演算法和D*演算法

Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。

Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。

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

大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。

提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。

A*（A-Star)演算法是一種啟發式演算法，是靜態路網中求解最短路最有效的方法。

公式表示為： f(n)=g(n)+h(n),
其中f(n) 是節點n從初始點到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n)是從n到目標節點最佳路徑的估計代價。

保證找到最短路徑（最優解的）條件，關鍵在於估價函數h(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。
如果 估價值>實際值, 搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。
估價值與實際值越接近，估價函數取得就越好。
例如對於幾何路網來說，可以取兩節點間歐幾理德距離（直線距離）做為估價值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}

A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。

動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。

D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。

主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。

D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。

6. 什麼是 a演算法a* 演算法有什麼特點

A*演算法：A*（A-Star)演算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好
A* （A-Star)演算法是一種靜態路網中求解最短路最有效的直接搜索方法。
注意是最有效的直接搜索演算法。之後涌現了很多預處理演算法（ALT，CH，HL等等），在線查詢效率是A*演算法的數千甚至上萬倍。
公式表示為： f(n)=g(n)+h(n),
其中 f(n) 是從初始點經由節點n到目標點的估價函數，
g(n) 是在狀態空間中從初始節點到n節點的實際代價，
h(n) 是從n到目標節點最佳路徑的估計代價。
保證找到最短路徑（最優解的）條件，關鍵在於估價函數f(n)的選取：
估價值h(n)<= n到目標節點的距離實際值，這種情況下，搜索的點數多，搜索范圍大，效率低。但能得到最優解。並且如果h(n)=d(n)，即距離估計h(n)等於最短距離，那麼搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。
如果 估價值>實際值,搜索的點數少，搜索范圍小，效率高，但不能保證得到最優解。

7. 求A到B之間的最短路徑，怎麼獲取

問題：從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑——最短路徑。解決最短路的問題有以下演算法，Dijkstra演算法，Bellman-Ford演算法，Floyd演算法和SPFA演算法，另外還有著名的啟發式搜索演算法A*，不過A*准備單獨出一篇，其中Floyd演算法可以求解任意兩點間的最短路徑的長度。任意一個最短路演算法都是基於這樣一個事實：從任意節點A到任意節點B的最短路徑不外乎2種可能，1是直接從A到B，2是從A經過若干個節點到B。
(1) 迪傑斯特拉(Dijkstra)演算法按路徑長度(看下面表格的最後一行，就是next點)遞增次序產生最短路徑。先把V分成兩組：
S：已求出最短路徑的頂點的集合
V-S=T：尚未確定最短路徑的頂點集合
將T中頂點按最短路徑遞增的次序加入到S中，依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值或是從V0經S中頂點到Vk的路徑權值之和（反證法可證，說實話，真不明白哦）。
(2) 求最短路徑步驟
初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值， 若存在<V0,Vi>，為<V0,Vi>弧上的權值（和SPFA初始化方式不同），若不存在<V0,Vi>，為Inf。
從T中選取一個其距離值為最小的頂點W(貪心體現在此處)，加入S(注意不是直接從S集合中選取，理解這個對於理解vis數組的作用至關重要)，對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值（上面兩個並列for循環，使用最小點更新）。
重復上述步驟，直到S中包含所有頂點，即S=V為止（說明最外層是除起點外的遍歷）。