A. 圖遍歷演算法之最短路徑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/
B. Dijkstra演算法
Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。注意該演算法要求圖中不存在負權邊。
設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以後每求得一條最短路徑 , 就將加入到集合S中，直到全部頂點都加入到S中，演算法就結束了），第二組為其餘未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大於從源點v到U中任何頂點的最短路徑長度含侍仿。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。
（1）初始時，S只包含起點D；U包含除D外的其他頂點，且U中頂點的距離為「起點D到該頂點的距離」（例如，U中頂點A的距離為[D,A]的長度，然後D和A不相鄰，則談棗A的距離為∞）
（2）從U中選出「距離最短的頂點K」，並將頂點K加入到S中；同時，從U中移除頂點K
（3）更新U中各個頂點到起點D的距離。之所以更新U中頂點的距離，是由於上一步談纖中確定了K是求出最短路徑的頂點，從而可以利用K來更新其他頂點到起點D的距離（例如，[D,A]的距離可能大於[D,K]+[K,A]的距離）
（4）重復步驟（2）和（3），直到遍歷完所有頂點
https://blog.csdn.net/yalishadaa/article/details/55827681
C. Ackerman函數的動態規范演算法
試設計一個計算A(m，n)的動態規劃演算法，該演算法只佔用O(m)空間。
用兩個一維數組，ind[i]和val[i]，使得當ind[i]等於t時，val[i]=A(i，ind[i])。
i ind[i] val[i]
0 0 1
1 -1 0
2 -1 0
……
初始時，令ind[0]=0，val[0]=1，ind[i]=-1(i>0)，val[i]=0(i>0)。
1當m=0時，A(m，n)=n+1。
任給一個t，當ind[0]=t時，能夠求出val[0]的值，val[0]等於ind[0]。
2當n=0，m>0時，A(m，n)=n+1。
能夠求出當ind[i]=0時，val[i]的值，此時val[i]等於當ind[i-1]等於1時val[i-1]的值。
3當m>0，n>0時，A(m，n)=A(m-1，A(m，n-1))。
當ind[i]=t，val[i]=s時，要求當ind[i]』=t+1時val[i]』的值。
Val[i]』=A(i，ind[i]』)=A(i-1，A(i，ind[i]』-1)=A(i-1，A(i，ind[i]))=A(i-1，val[i])
所以，當ind[i-1]=val[i]時，能夠求出當ind[i]』=k+1時，val[i]』=val[i-1]。
#include <stdio.h>
int ack(int& m,int& n)
{
int i,j;
int *val=new int[m+1];
int *ind=new int[m+1];
for(i=1;i<=m;i++)
{
ind[i]=-1;
val[i]=-1;
}
ind[0]=0;
val[0]=1;
while(ind[m]<n)
{
val[0]++;
ind[0]++;
printf("%d ",val[0]);
for(j=1;j<=m;j++)
{
if(1==ind[j-1])
{
val[j]=val[j-1];
ind[j]=0;
}
if(val[j]!=ind[j-1])
break;
ind[j]++;
val[j]=val[j-1];
}
}
printf("\n");
printf(" i ind[i] val[i]\n");
for(i=0;i<=m;i++)
printf("%5d %6d %6d\n",i,ind[i],val[i]);
return val[m];
}
D. 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