學完了圖論基礎(一)和圖論基礎(二)之後，我們學會了如何儲存一個圖、周遊一個圖。而這篇文章，将帶大家領略圖論最精彩的地方——單源最短路。
單源最短路，就是指在一個圖中，對于一個點，求出這個點到剩下所有點的最短距離。就像算學校到北京各個角落的最短距離一樣。目前，有兩種算法可以解決這個問題：Dijkstra和Bellman-Ford。而今天這篇文章，将給大家帶來Dijkstra單源最短路算法的詳解。
在介紹Dijkstra算法之前，先稍微介紹一下它的發明者：
Edsger Wybe Dijkstra(1930.5.11~2002.8.6)
荷蘭計算機科學家。
生于科學家庭，畢業于荷蘭Leiden大學。
提出“goto有害論”，設計開發THE作業系統，提出信号量和PV原語，發明銀行家算法，發明Dijkstra單源最短路算法。
獲得1972有“計算機學諾貝爾獎”之稱的圖靈獎。
既然這樣的圖靈獎大佬，都用自己的姓氏“Dijkstra”來命名這樣一個算法，足以可見這個算法的在的重要性和它的偉大之處。但是這個偉大的算法也不失它有趣而且易懂的一面。下面，就給大家詳細解釋Dijkstra算法是如何運作的。
首先，我們先明确一下目标。我們的目标是對于一個圖，找到這個圖一個點到所有點的距離。拿這個可愛的無向圖舉例：
我們的目标就是求1号點到所有點的距離。那麼，這個怎麼實作呢？
有一種很容易想到的方法就是把所有方法都走一遍，然後選出一種距離最短的走法，作為答案。這樣的答案固然正确，但是這種做法在資訊競賽中叫做“暴力”，意思是它雖然很容易想到，但是運作的太慢了。有沒有一種方式，能更迅速地找到最短的距離？
考慮一種情況。假設你現在在你家(1号點)，你隻知道你家到學校(2号點)的最短距離為5和到公園(3号點)的最短距離為8。你現在想知道你家到咖啡廳(4号點)的最短距離，但是，你家并沒有直接到咖啡廳的路。現在，想到咖啡廳就有兩種選擇，第一種是先到學校再去咖啡廳；另一種是先到公園再去咖啡廳，哪一種更快？
答案顯然是第一種，第二種我們根本不用計算就知道不可行。因為第一種到學校的5加上到咖啡廳的1之後，發現這個距離是6。這個距離比到公園的都要短，說明就算公園到咖啡廳特别短，甚至挨着咖啡廳，我們都不可能會走公園這條路。這樣就省的計算公園這條路了。這種“省的計算”，就是一種優化。
而這樣可以推斷，任何一個和學校相連的地方，如果它到學校的距離+5小于8，我們就根本不用考慮從公園走的路線。這樣，優化的計算量就會大很多了。
那麼這樣的“減少計算量”的政策，如何應用于算法中呢？當我們确定到一個點u的最短距離為k時，我們枚舉所有以這個點為起點的邊。對于每一條這樣的邊，假設它的終點為v，長度為q。我們就得到一種到u的方式，也就是先走k的距離，到達u，然後再走q的距離，到達v。這樣一種方式不一定是最短的，但是，如果這個方式比以前的所有方式都短，我們可以它當作一個"估計距離"。對于其他的點也是一樣。也就是，我們的圖會成為這個樣子：
這個圖中，一些黑色的點就是已經确定最短距離的點，而從這些黑色的點到那些藍色點的距離因為還沒有确定下來，是以叫“估計距離"。這個時候，把所有的"估計距離"到達的點中最短的"估計距離"确定為最短距離就可以了，也就相當于算出源點到這個點的距離了。
舉個例子，如果上面的u是所有以藍點為終點的點中"估計距離"離源點最近的，那麼就可以把藍線變成黑線了，相當于确定了1到i到u為從1到u的最短路徑。
為什麼這個是正确的呢？因為就像剛才到咖啡廳的例子，因為這個估計距離是最短的，是以就不用計算通過其他的點再到這個點的距離了。如果拿剛才的圖舉例，就是這個樣子：
如果u是所有以藍點為終點的點中"估計距離"離源點最近的，那麼這種通過其他的藍線再經過紅線再到達u的路徑就應該被舍棄了。因為到達和u同一層的點的時候，距離已經比從1到i到u的長了，就算這些紅線再短，也不可能通過它們到u點了。就好比從家到學校再到咖啡廳的距離已經比從家到公園的短了，就不可能通過公園到咖啡廳了。
把一個估計距離确定為最短距離後，需要再按上面的步驟枚舉每一條出邊，更新其他點的估計距離。然後再重複以上步驟，直到所有的點的最短距離确定下來，運作結束。
概括一下剛才的步驟：
1、把這個圖分為兩個點集，一個叫S，代表确定最短距離的點集。另一個叫T，代表沒有确定最短距離的點集。
2、每個點都有一個值dis[i]，代表源點到它的距離。如果點i在S集合，說明這是它到源點的最短距離。如果在T集合，說明這是它的估計距離。(除源點dis為0之外，開始的無限大)
3、選取T集合裡面dis值最小點u的，加入到S集合，相當于計算出源點到u的最短距離。
4、周遊u所有的出邊，對于每一條出邊和這條出邊的終點v，令dis[v]=min(dis[v],dis[u]+這條邊長度)，也就是更新所有出邊終點的“估計距離”
5、重複3、4步，直到所有的點都加入S集合，算法結束。
好了，現在我們模拟一下這個步驟：
這是資料：
5 6 1 2 5 1 3 8 2 3 1 2 4 3 4 5 7 2 5 2
圖呢，長成這個樣子：
我們以1為源點，求1到所有點的最短路。
開始，我們先把dis數組賦好初始值，也就是除了dis[1]=0之外，其他的都是無限。
開始，我們先把起點，也就是1号點，加入S集合。然後搜尋所有1号點的出邊，發現了2号點。從1号點到2号點是5，比原來dis[2]的無限要小，是以更新dis[2]=5，也就是2的估計距離是5。然後發現了3号點，把dis[3]更新為8，也就是其估計距離為8。這時的dis數組是這樣的：
dis[0,5,8,∞,∞]
然後，把所有估計距離最小的點加入點集S，也就是2号點加入點集S，确定其最短距離為5。然後搜尋所有2的出邊，先是5号點，把dis[5]，也就是5号點的估計距離更新為dis[2]+2=7。然後是4号點，把dis[4]更新為8，最後是3号點。本來3号點的估計距離是8，但是dis[2]+1=6,比8小，是以将dis[3]更新為6。
dis[0,5,6,8,7]
然後，再把估計距離最小的3号點加入點集S，确定最短距離為6，然後搜尋3的所有出邊，發現沒有可以更新的。
然後分别是5号點和4号點，依次把它們加入到點集S，确定其最短路徑，它們也沒有可以更新的。是以算法結束，最後的答案就是：
dis[0,5,6,8,7]
這代表着源點1到所有點的最短路了。
那麼具體的代碼實作如下(鄰接矩陣的)
#include #include #include #include #include #include using namespace std;int map[110][110];//這就是map數組，鄰接矩陣存圖 int dis[10010];//dis數組，存儲估計值int book[10010];//book[i]代表這個點是否再S集合中 int n,m;void dijkstra(int u)//主函數，參數是源點編号{ memset(dis,127,sizeof(dis));//把dis數組附最大值 int start=u;//先從源點搜尋 book[start]=1;//把源點加入S集合 for(int i=1;i<=n;i++) { dis[i]=min(dis[i],map[start][i]);//先更新一遍 } for(int i=1;i<=n-1;i++) { int minn=2147483647; for(int j=1;j<=n;j++) if(book[j]==0 && minn>dis[j]) { minn=dis[j]; start=j;//找到T集合中估計距離最近的點 } book[start]=1; //加入S集合 for(int j=1;j<=n;j++) dis[j]=min(dis[j],dis[start]+map[start][j]);//以新的點來更新dis。 }}int main(){ cin>>n>>m; memset(map,127,sizeof(map)); for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; map[a][b]=c; map[b][a]=c; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) map[i][j]=0; dijkstra(1);//以1為源點。 for(int i=1;i<=n;i++) cout<" ";}
運作結果如下：
目前來看，對于每一次把S集合的點移動到T集合，需要枚舉每一個節點來找到最小估計距離的點，需要消耗O(n)的時間，而一共要進行n次操作，是以是O(n²)的時間複雜度。
但是，用鄰接表來實作的話，可以讓時間複雜度減少一些常數。
代碼如下：
#include #include #include #include #include #include using namespace std;int value[10010],to[10010],next[10010];int head[10010],total;int book[10010];int dis[10010];int n,m;void adl(int a,int b,int c){ total++; to[total]=b; value[total]=c; next[total]=head[a]; head[a]=total;}void dijkstra(int u){ memset(dis,88,sizeof(dis)); memset(book,0,sizeof(book)); dis[u]=0; for(int i=1;i<=n;i++) { int start=-1; for(int j=1;j<=n;j++) if(book[j]==0 && (dis[start]>dis[j] || start==-1)) start=j; book[start]=1; for(int e=head[start];e;e=next[e])//注意，這裡把枚舉點便成了枚舉start的出邊 dis[to[e]]=min(dis[to[e]],dis[start]+value[e]); }}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; adl(a,b,c); adl(b,a,c); } dijkstra(1); for(int i=1;i<=n;i++) cout<" ";}
運作結果如下：
還可以更加優化嗎？在Dijkstra算法中，每次需要找出估計距離最小的節點，這樣每次需要消耗O(n)的時間，可不可以把這個過程優化？可以考慮用優先隊列。
優先隊列，就是一個類似于隊列的STL資料結構，可以對内元素進行排序。
當我們更新一個點的估計距離時，我們把它放進一個優先隊列中。這樣，優先隊列的隊首永遠是估計距離最小的點，每次隻需要取隊首元素就可以了。
代碼實作如下：
#include #include #include #include #include #include #define N 100010using namespace std;int total,head[N],nxt[N<<1],val[N<<1],to[N<<1];int n,m,dis[N],book[N];void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ;}struct node{//重載運算符，便于比較 int dis,index; bool operator < (const node& a) const{ return dis > a.dis; }}P[N];priority_queue Q;void Dijkstra(){ memset(dis,127,sizeof(dis)); dis[1]=0; Q.push(node{0,1}); while(!Q.empty()){ int u=Q.top().index;Q.pop();//取出隊首元素，一定是估計距離最小的 if(book[u]) continue; book[u]=1; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; Q.push(node{dis[to[e]],to[e]}); } } return ;}int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; adl(a,b,c); adl(b,a,c); } Dijkstra(); for(int i=1;i<=n;i++) cout<" "; return 0;}
運作結果如下：
優先隊列的實作方法是堆，是以其複雜度大約在O(logN)左右。這樣整個優先隊列優化的Dijkstra複雜度就是O(NlogN)了。
當然，Dijkstra也有它不足的地方。上文曾經說過，當你已知從家到學校再到咖啡廳的距離比從家到公園要小時，就不用考慮從家到公園再到咖啡廳這回事了。但是，有一種情況，是需要考慮的！就是，如果從公園到咖啡廳的距離是負數(是的你沒聽錯)就不能忽略這種情況！這就是圖論中的負權邊，而這種負權邊，也正是Dijkstra解決不了的。想要解決負權邊問題，就要看下一篇Bellman-Ford詳解了！
在文章的最後，在說點關于筆者名字"Dijkstra"的内容吧。
Dijkstra是一個荷蘭名字，它并不符合自然拼讀的規律，是以延伸出出很多讀法：
1、重音放在"戴"上，k不發音，戴潔斯欻(chua)
2、重音放在”迪"上，k不發音，狄潔斯欻
3、重音放在"迪"上，j不發音，狄克斯欻
4、重音放在"戴"上，戴潔克斯欻
5、重音放在“基"上，狄基克斯欻
6、重音放在”戴"上，j不發音，戴剋(kei)斯欻
至于我為什麼選擇這個英文名，故事是這樣的。我原來英文名叫Jason。在初一那年，去了加拿大的一個夏校，發現和另一個中國同學重名了。而且我覺得這個名字并不是那麼進階，于是打算換一個英文名。當時正在學習圖論，于是想選一個算法作為英文名。考慮過Floyd，但是因為這個算法時間複雜度太高了，是以沒選。又考慮過Tarjan，但是這個名字似乎已經被一個資訊競賽大佬選過了。而且，我總不能叫"Bellman-Ford",這本來就是兩個人的名字。最後挑選了Dijkstra。這個名字雖然不符合自然拼讀，但是它卻很有資訊技術色彩。i、j、k是循環常用的變量，str又是string的簡稱。而且這個名字看起來也十分好看，最終選擇了這個名字。
然後，這個名字又給我帶來了許多成就。回國後，我建立了一個名叫Dijkstra的部落格。又在上面發了一個類似這篇文章的《Dijkstra算法詳解》結果因為标題出現了兩次Dijkstra，是以隻要别人百度上搜Dijkstra，就能在首頁看到我的部落格。突然間，這篇部落格收獲了7w多的閱讀量，也給予我寫更多部落格的信心。
言歸正傳，這篇文章帶大家學習了Dijkstra算法，并且證明了它的正确性。還附加了優先隊列的優化。在下周的文章中，将介紹Bellman-Ford算法，以解決Dijkstra無法解決的負權邊問題。