前言
本專題旨在快速了解常見的數(shù)據(jù)結(jié)構(gòu)和算法羊壹。
在需要使用到相應算法時每窖，能夠幫助你回憶出常用的實現(xiàn)方案并且知曉其優(yōu)缺點和適用環(huán)境。并不涉及十分具體的實現(xiàn)細節(jié)描述恨锚。
圖的最短路徑算法
最短路徑問題是圖論研究中的一個經(jīng)典算法問題型奥，旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑瞳收。
算法具體的形式包括：
- 確定起點的最短路徑問題：即已知起始結(jié)點，求最短路徑的問題厢汹。適合使用Dijkstra算法螟深。
- 確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結(jié)結(jié)點烫葬，求最短路徑的問題血崭。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點的問題厘灼。
- 確定起點終點的最短路徑問題：即已知起點和終點，求兩結(jié)點之間的最短路徑咽瓷。
- 全局最短路徑問題：求圖中所有的最短路徑设凹。適合使用Floyd-Warshall算法。
主要介紹以下幾種算法：
- Dijkstra最短路算法（單源最短路）
- Bellman–Ford算法（解決負權(quán)邊問題）
- SPFA算法（Bellman-Ford算法改進版本）
- Floyd最短路算法（全局/多源最短路）
常用算法
Dijkstra最短路算法（單源最短路）
圖片例子和史料來自：http://blog.51cto.com/ahalei/1387799
算法介紹：
迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑問題茅姜，算法最終得到一個最短路徑樹闪朱。該算法常用于路由算法或者作為其他圖算法的一個子模塊。
指定一個起始點（源點）到其余各個頂點的最短路徑钻洒，也叫做“單源最短路徑”奋姿。例如求下圖中的1號頂點到2、3素标、4称诗、5、6號頂點的最短路徑头遭。
使用二維數(shù)組e來存儲頂點之間邊的關(guān)系寓免，初始值如下癣诱。
我們還需要用一個一維數(shù)組dis來存儲1號頂點到其余各個頂點的初始路程，如下袜香。
將此時dis數(shù)組中的值稱為最短路的“估計值”撕予。
既然是求1號頂點到其余各個頂點的最短路程，那就先找一個離1號頂點最近的頂點蜈首。通過數(shù)組dis可知當前離1號頂點最近是2號頂點实抡。當選擇了2號頂點后，dis[2]的值就已經(jīng)從“估計值”變?yōu)榱恕按_定值”欢策，即1號頂點到2號頂點的最短路程就是當前dis[2]值吆寨。
既然選了2號頂點，接下來再來看2號頂點有哪些出邊呢猬腰。有2->3和2->4這兩條邊鸟废。先討論通過2->3這條邊能否讓1號頂點到3號頂點的路程變短。也就是說現(xiàn)在來比較dis[3]和dis[2]+e[2][3]的大小姑荷。其中dis[3]表示1號頂點到3號頂點的路程盒延。dis[2]+e[2][3]中dis[2]表示1號頂點到2號頂點的路程，e[2][3]表示2->3這條邊鼠冕。所以dis[2]+e[2][3]就表示從1號頂點先到2號頂點添寺，再通過2->3這條邊，到達3號頂點的路程懈费。
這個過程有個專業(yè)術(shù)語叫做“松弛”计露。松弛完畢之后dis數(shù)組為：
接下來，繼續(xù)在剩下的3憎乙、4票罐、5和6號頂點中，選出離1號頂點最近的頂點4泞边，變?yōu)榇_定值该押，以此類推。
最終dis數(shù)組如下阵谚，這便是1號頂點到其余各個頂點的最短路徑蚕礼。
核心代碼：
//Dijkstra算法核心語句
for(i=1;i<=n-1;i++)
{
//找到離1號頂點最近的頂點
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0 && dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(v=1;v<=n;v++)
{
if(e[u][v]<inf)
{
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
關(guān)于復雜度：
- M：邊的數(shù)量
- N：節(jié)點數(shù)量
通過上面的代碼我們可以看出，我們實現(xiàn)的Dijkstra最短路算法的時間復雜度是O(N^2)梢什。其中每次找到離1號頂點最近的頂點的時間復雜度是O(N)奠蹬。
優(yōu)化:
這里我們可以用“堆”（以后再說）來優(yōu)化，使得這一部分的時間復雜度降低到
O(logN)嗡午。另外對于邊數(shù)M少于
N^2的稀疏圖來說（我們把M遠小于N^2的圖稱為稀疏圖囤躁，而M相對較大的圖稱為稠密圖），我們可以用鄰接表來代替鄰接矩陣，使得整個時間復雜度優(yōu)化到O((M+N)logN)割以。請注意金度！在最壞的情況下M就是
N^2，這樣的話MlogN要比N^2還要大严沥。但是大多數(shù)情況下并不會有那么多邊猜极，因此(M+N)logN要比N^2小很多。
Dijkstra思想總結(jié)：
dijkstra算法本質(zhì)上算是貪心的思想消玄，每次在剩余節(jié)點中找到離起點最近的節(jié)點放到隊列中跟伏，并用來更新剩下的節(jié)點的距離，再將它標記上表示已經(jīng)找到到它的最短路徑翩瓜，以后不用更新它了受扳。這樣做的原因是到一個節(jié)點的最短路徑必然會經(jīng)過比它離起點更近的節(jié)點，而如果一個節(jié)點的當前距離值比任何剩余節(jié)點都小兔跌，那么當前的距離值一定是最小的勘高。（剩余節(jié)點的距離值只能用當前剩余節(jié)點來更新，因為求出了最短路的節(jié)點之前已經(jīng)更新過了）
dijkstra就是這樣不斷從剩余節(jié)點中拿出一個可以確定最短路徑的節(jié)點最終求得從起點到每個節(jié)點的最短距離坟桅。
用鄰接表代替鄰接矩陣存儲
參考：http://blog.51cto.com/ahalei/1391988
總結(jié)如下：
可以發(fā)現(xiàn)使用鄰接表來存儲圖的時間空間復雜度是O(M)华望，遍歷每一條邊的時間復雜度是也是O(M)。如果一個圖是稀疏圖的話仅乓，M要遠小于N^2赖舟。因此稀疏圖選用鄰接表來存儲要比鄰接矩陣來存儲要好很多。
Bellman–Ford算法（解決負權(quán)邊問題）
思想：
bellman-ford算法進行n-1次更新（一次更新是指用所有節(jié)點進行一次松弛操作）來找到到所有節(jié)點的單源最短路夸楣。
bellman-ford算法和dijkstra其實有點相似宾抓，該算法能夠保證每更新一次都能確定一個節(jié)點的最短路，但與dijkstra不同的是豫喧，并不知道是那個節(jié)點的最短路被確定了石洗，只是知道比上次多確定一個，這樣進行n-1次更新后所有節(jié)點的最短路都確定了（源點的距離本來就是確定的）紧显。
現(xiàn)在來說明為什么每次更新都能多找到一個能確定最短路的節(jié)點：
1.將所有節(jié)點分為兩類：已知最短距離的節(jié)點和剩余節(jié)點劲腿。
2.這兩類節(jié)點滿足這樣的性質(zhì)：已知最短距離的節(jié)點的最短距離值都比剩余節(jié)點的最短路值小。（這一點也和dijkstra一樣）
3.有了上面兩點說明鸟妙，易知到剩余節(jié)點的路徑一定會經(jīng)過已知節(jié)點
4.而從已知節(jié)點連到剩余節(jié)點的所有邊中的最小的那個邊，這條邊所更新后的剩余節(jié)點就一定是確定的最短距離挥吵，從而就多找到了一個能確定最短距離的節(jié)點重父，不用知道它到底是哪個節(jié)點。
bellman-ford的一個優(yōu)勢是可以用來判斷是否存在負環(huán)忽匈，在不存在負環(huán)的情況下房午，進行了n-1次所有邊的更新操作后每個節(jié)點的最短距離都確定了，再用所有邊去更新一次不會改變結(jié)果丹允。而如果存在負環(huán)郭厌，最后再更新一次會改變結(jié)果袋倔。原因是之前是假定了起點的最短距離是確定的并且是最短的，而又負環(huán)的情況下這個假設不再成立折柠。
Bellman-Ford 算法描述：
- 創(chuàng)建源頂點 v 到圖中所有頂點的距離的集合 distSet宾娜，為圖中的所有頂點指定一個距離值，初始均為 Infinite扇售，源頂點距離為 0前塔；
- 計算最短路徑，執(zhí)行 V - 1 次遍歷承冰；
- 對于圖中的每條邊：如果起點 u 的距離 d 加上邊的權(quán)值 w 小于終點 v 的距離 d华弓，則更新終點 v 的距離值 d；
- 檢測圖中是否有負權(quán)邊形成了環(huán)困乒，遍歷圖中的所有邊寂屏，計算 u 至 v 的距離，如果對于 v 存在更小的距離娜搂，則說明存在環(huán)迁霎；
偽代碼：
BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
for i 1 to |V[G]| - 1
do for each edge (u, v) E[G]
do RELAX(u, v, w)
for each edge (u, v) E[G]
do if d[v] > d[u] + w(u, v)
then return FALSE
return TRUE
SPFA（Bellman-Ford算法改進版本）
SPFA算法是1994年西安交通大學段凡丁提出
spfa可以看成是bellman-ford的隊列優(yōu)化版本，正如在前面講到的涌攻，bellman每一輪用所有邊來進行松弛操作可以多確定一個點的最短路徑欧引，但是用每次都把所有邊拿來松弛太浪費了，不難發(fā)現(xiàn)恳谎，只有那些已經(jīng)確定了最短路徑的點所連出去的邊才是有效的芝此，因為新確定的點一定要先通過已知(最短路徑的)節(jié)點。
所以我們只需要把已知節(jié)點連出去的邊用來松弛就行了因痛，但是問題是我們并不知道哪些點是已知節(jié)點婚苹，不過我們可以放寬一下條件，找哪些可能是已知節(jié)點的點鸵膏，也就是之前松弛后更新的點膊升，已知節(jié)點必然在這些點中。
所以spfa的做法就是把每次更新了的點放到隊列中記錄下來谭企。
偽代碼：
ProcedureSPFA;
Begin
initialize-single-source(G,s);
initialize-queue(Q);
enqueue(Q,s);
while not empty(Q) do begin
u:=dequeue(Q);
for each v∈adj[u] do begin
tmp:=d[v];
relax(u,v);
if(tmp<>d[v])and(not v in Q)then enqueue(Q,v);
end;
end;
End;
如何看待 SPFA 算法已死這種說法廓译？
來自：https://www.zhihu.com/question/292283275/answer/484694411
在非負邊權(quán)的圖中，隨手卡 SPFA 已是業(yè)界常識债查。在負邊權(quán)的圖中非区，不把 SPFA 卡到最慢就設定時限是非常不負責任的行為，而卡到最慢就意味著 SPFA 和傳統(tǒng) Bellman Ford 算法的時間效率類似盹廷，而后者的實現(xiàn)難度遠低于前者征绸。
Floyd最短路算法（全局/多源最短路）
圖片例子和史料來自：https://www.cnblogs.com/ahalei/p/3622328.html
此算法由Robert W. Floyd（羅伯特·弗洛伊德）于1962年發(fā)表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍爾）也獨立發(fā)表了這個算法。Robert W．Floyd這個牛人是朵奇葩管怠，他原本在芝加哥大學讀的文學淆衷，但是因為當時美國經(jīng)濟不太景氣，找工作比較困難渤弛，無奈之下到西屋電氣公司當了一名計算機操作員祝拯，在IBM650機房值夜班，并由此開始了他的計算機生涯暮芭。此外他還和J.W.J. Williams（威廉姆斯）于1964年共同發(fā)明了著名的堆排序算法HEAPSORT鹿驼。
算法介紹：
上圖中有4個城市8條公路，公路上的數(shù)字表示這條公路的長短辕宏。請注意這些公路是單向的畜晰。我們現(xiàn)在需要求任意兩個城市之間的最短路程，也就是求任意兩個點之間的最短路徑瑞筐。這個問題這也被稱為“多源最短路徑”問題凄鼻。
現(xiàn)在需要一個數(shù)據(jù)結(jié)構(gòu)來存儲圖的信息，我們?nèi)匀豢梢杂靡粋€4*4的矩陣（二維數(shù)組e）來存儲聚假。
核心代碼：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
這段代碼的基本思想就是：
最開始只允許經(jīng)過1號頂點進行中轉(zhuǎn)块蚌，接下來只允許經(jīng)過1和2號頂點進行中轉(zhuǎn)……允許經(jīng)過1~n號所有頂點進行中轉(zhuǎn)，求任意兩點之間的最短路程膘格。一旦發(fā)現(xiàn)比之前矩陣內(nèi)存儲的距離短峭范，就用它覆蓋原來保存的距離。
用一句話概括就是：從i號頂點到j號頂點只經(jīng)過前k號點的最短路程瘪贱。
另外需要注意的是：Floyd-Warshall算法不能解決帶有“負權(quán)回路”（或者叫“負權(quán)環(huán)”）的圖纱控，因為帶有“負權(quán)回路”的圖沒有最短路。例如下面這個圖就不存在1號頂點到3號頂點的最短路徑菜秦。因為1->2->3->1->2->3->…->1->2->3這樣路徑中甜害，每繞一次1->-2>3這樣的環(huán)，最短路就會減少1球昨，永遠找不到最短路尔店。其實如果一個圖中帶有“負權(quán)回路”那么這個圖則沒有最短路。
代碼實現(xiàn)：
#include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf(infinity的縮寫)存儲一個我們認為的正無窮值
//讀入n和m主慰，n表示頂點個數(shù)嚣州，m表示邊的條數(shù)
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//讀入邊
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//Floyd-Warshall算法核心語句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j] )
e[i][j]=e[i][k]+e[k][j];
//輸出最終的結(jié)果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
總結(jié)
關(guān)于BellmanFord和SPFA再說兩句
來自：https://www.zhihu.com/question/27312074
SPFA只是BellmanFord的一種優(yōu)化，其復雜度是O(kE)共螺，SPFA的提出者認為k很小避诽，可以看作是常數(shù)，但事實上這一說法十分不嚴謹（原論文的“證明”竟然是靠編程驗證璃谨，甚至沒有說明編程驗證使用的數(shù)據(jù)是如何生成的），如其他答案所說的，在一些數(shù)據(jù)中佳吞，這個k可能會很大拱雏。而Dijkstra算法在使用斐波那契堆優(yōu)化的情況下復雜度是O(E+VlogV)。SPFA底扳，或者說BellmanFord及其各種優(yōu)化（姜碧野的國家集訓隊論文就提到了一種棧的優(yōu)化）的優(yōu)勢更主要體現(xiàn)在能夠處理負權(quán)和判斷負環(huán)吧（BellmanFord可以找到負環(huán)铸抑，但SPFA只能判斷負環(huán)是否存在）。
補充算法
還有一些最短路算法的優(yōu)化或者引申方法衷模，感興趣可以谷歌一下：
- Johnson算法
- Bi-Direction BFS算法
- ...
