浙江大學-數據結構-小白專場：最小路徑問題-7.1.3

有權圖的單源最短路演算法

我們先來看一個例子，假如說我們把V1選作成我們的源點，把V6選作成我們的終點

那麼從V1到V6最短的路徑是哪一條呢？我們的答案是這條路徑

你要注意到有權圖的最短路跟無權圖的最短路一個很大的區別在於有權圖的最短路它不一定是經過頂點數最少的那條路，經過最少的應該是V1->V4->V6,但是這條路徑上面的權重和是1+8 = 9， 而正確答案是1+4+1 = 6,實際上這條路更短，於是呢，我們整個的演算法肯定跟無權圖的演算法就要有點區別，要更複雜一點，如果某條邊的權重是負的，會發生什麼情況呢？那麼我在這裡頭可以有這麼一個理解，我把每條邊上的權重理解為如果是正數是我要給別人錢，如果是負數代表我收別人錢，

於是我走一圈我就凈賺5塊錢，所以呢，什麼叫最短路呢？即什麼叫最便宜的路呢？我只要在這不停的兜圈子，我的收入會是無窮大，所以這條路徑的花銷應該是負無窮，那這種情況呢，叫一個負值圈(negative-cost cycle),如果圖裡面有這樣一個負值圈，我們基本上所有的演算法都掛掉

所以我們在後面討論的時候，不考慮這種情況，那麼整個的問題要怎麼想呢？其實它的思路跟無權圖的單源最短路演算法還是有一定相似之處的，其實可以認為無權圖是一種特殊的有權圖，只不過每條邊上權重為1就是了，所以它們的演算法肯定有相通之處，最重要的一個特點都是按照遞增的順序或者叫非遞減的順序找出固定的源點到各個頂點的最短路，解決這個問題的演算法有一個金光閃閃的名字，叫Dijkstra演算法

Dijkstra演算法其實跟前面講的BFS相似的地方在於都是把頂點一個一個往集合裡面收的，所以在這先定義一個頂點的集合，叫作S, 它裡面包含的是什麼呢？初始狀態下只包含源點，然後隨著演算法一步一步的進行，我們把一個一個的頂點往裡收，收進來的頂點它們的最短路徑都是最後已經確認了的，我們仍然像前面的演算法一樣，定義一個距離的數組，叫dist, 對於任何一個沒有被收錄的頂點v,我們把dist[v]定義為從源點到v的最短路徑長度，但是這不是最終的最短路徑，這個路徑僅僅經過這個集合裡面已經收集到的頂點，也就是說從s到v,但中間經停的僅僅是這個集合裡面的頂點，這條路徑的最小長度，那麼我們要說這個最小長度呢，多半不是最終的最小長度，但是隨著一個一個頂點不斷的被加到集合里，這個dist[v]會慢慢的變小變小，

一直到最後被完善到成為真正的最短路徑，當它成為真正的最短路徑的時候，這個v就被收到了集合裡面，這個演算法能夠執行的很重要的前提假設，是說我們的路徑是按照遞增或者非遞減的順序生成的，因為我們是按照這個順序生成的，所以當我們要把v下一個v收到頂點裡去的時候，這個v真正的最短路必須只經過S中的頂點，不會經過S外面的頂點，我們想這個問題可以用反證法的思路來想，假如這麼說是不對的，假如說我下一個要把v收進去的時候，從s到v這個路徑上還存在另外一個點w,這個w是在這個s以外的，那麼我從s到v,一定要從s到w,再從w到v,這個時候就會有矛盾，什麼矛盾呢？s到w的距離顯然小於s到v的距離，而v呢，是下一個馬上要被收進去的頂點，而我們的路徑是按照遞增的路徑生成的，就意味著凡是距離比例要小的那些頂點都應該在它之前就已經被收進去了，w到s的距離顯然比v到s的距離要小，所以w肯定應該已經在s這個集合裡面了，不可能在外面，所以我們就有了結論，真正的最短路一定是只經過S中的頂點的，所以我們想想應該怎麼做呢？所以每次可以看一下所有的dist裡面的最小值，還有哪個沒被收進去，然後把dist最小的那個收進去就好了，每次從沒有收錄的頂點中收錄一個dist最小的把它收進集合里去就好了，那這種思想就是貪心演算法的思想，什麼是貪心，後面還會再講

看上去，好像這個問題很簡單，已經解決了，但是你要小心，當我把一個v收到S裡面去的時候，它會不會影響其它頂點的最小長度呀？這就是我們的一個很嚴重的問題，把一個v加進S以後，可能影響另外一個頂點的dist值

它是會怎麼樣影響呢？如果把v加進去以後，這個w的距離就變小了的話，那麼v一定在從S到w的那個路徑上，把它加進去，才使它變小的，所以它一定會在路徑上，那這一點是比較好理解的，另外一個不太好理解的事實，v不僅在w的路徑上，而且從v到w，必定存在一條直接的邊，為什麼呢？為什麼不可能是s先到v,v再經過另外一個頂點，然後另外一個頂點再到w呢，我們說這種情況是絕無可能的，就是因為路徑是按照遞增的順序生成的，如果v和w之間還有另外一個頂點的話，那麼這個頂點到源點的距離，一定比v到源點的距離要大，但是我們假設的是說，w的dist值應該是什麼？是從s到w,僅僅經過集合裡面的頂點，那條路徑的長度，那麼如果另外還有一個結點，在v後面的話，那這個頂點不可能在s裡面，因為v是新增進去的，所以v應該是這個集合裡面距離最長的，所以一個v增加進去以後，會使得另外一個w的dist值變小的話，v一定在路徑上，並且v到w一定有一條直接的邊，換句話來說，就是w，一定是v的鄰接點，在說的清楚點，v增加進集合以後，它能影響的就是它的一圈鄰接點，所以在程序裡面，每當把v收進集合的時候，我們只要檢查它的一圈鄰接點，看看有沒有誰得到一個更小的dist值，更小的dist值可能是什麼呢？就是從源點到v的距離加上這條邊的權重，如果這個值更小，那麼我們更新一下w的距離，否則的話，這個距離保持不變

這個Dijkstra演算法的基本框架

我首先給了一個源點進去，然後呢，我是用一個循環去解決這個問題，每一次我要從沒有收錄的頂點中找一個dist最小的，然後我把它收到集合里去，這個收到集合裡面，我就簡單的定義了一個數組，叫collected，就是收進來了，在它收進來以後，我要檢查它的每一個鄰接點w,如果這個w還沒有被收進來，我要怎麼做呢？就像我們剛才說的，當v被收進來以後，從源點到v的距離加上這條邊的邊長，如果這是一個更小的距離的話(dist[V]+E<v,w> < dist[W]),那我們更新一下這個最短的距離(dist[W] = dist[V] + E<v,w>),與此同時呢，還得把V記錄在w的路徑上(path[W] = V),

這裡要想一下dist怎麼被初始化，首先呢，s的dist,應該是等於0的，這個道理非常顯然，自己到它自己是0，另外呢，就是凡是跟s直接相鄰的，s的每個鄰接點，它們的dist都可以直接被定義為s到w的權重，除此之外，再其它的那些頂點，跟s沒有直接邊相連的那些頂點，它應該被初始化什麼值呢？在Dijkstra這個演算法裡頭，這個dist可是不能被隨便的初始化，就因為有不等式在，我們當描述說一個頂點跟s沒有直接的路可以通的時候，一定要把它定義為正無窮，這樣的話，當我們發現一個更短的路徑的時候才可以把這個路徑往更小的地方去更新，你要想像如果我隨便把它定義為-1的話，那麼這個不等式永遠都不會成立了(dist[V]+E<v,w> < dist[W])，所以整個的演算法就不可能是正確的了，那基本上演算法就是這樣的運行過程，那注意到我們是在while（1）的循環裡頭,什麼時候要跳出來呢？跳出來的條件，應在在這(if (這樣的V不存在）break;),如果我找不到這樣的V了，也就是說所有的頂點，都已經被收錄了，那麼就從這直接跳出來，表示程序結束，這裡頭呢，還要注意一個問題，如果我們有一條邊是負的，Dijkstra演算法是不能解決有負邊的情況的，因為Dijkstra演算法的基本思路是說按照距離從小到大的順序去收集每一個頂點，如果有一條邊是負的，那麼對於某一個w來說，就有可能說有了dist[V]減掉了一個正值，我們就可以得到一個比V的距離還要短的W，而W之前是排在V的後面的，所以整個的演算法就會亂掉，如果碰到有負邊的情況要怎麼做呢？

這個留給大家自己去思考2333

接下來又是我們每次必問的老問題，這個演算法的時間複雜度是什麼呢？

其實演算法的時間複雜度，取決於我們是怎麼做V = 未收錄頂點中dist最小值，我們怎麼從沒收錄的頂點中找到距離最小的這一個，在我們決定了實現這一步的演算法以後(V = 未收錄頂點中dist最小者)，相應的就要決定實現這一步的演算法(dist[W] = dist[V] + E<v,w>), 你可能會覺得(dist[W] = dist[V] + E<v, w>)不就是一個簡單的賦值語句嗎，但是我要說的是這是一個偽碼描述，雖然看上去是一個簡單的賦值語句，但是呢，它其實的意思只是說，如果我有一個更短的距離，那我要把這個值更新成最短的距離，這個更新不一定是一個簡單的賦值，那要解決這個問題，其實我們有不止一種方法，

一個最簡單粗暴的方法，直接掃描所有沒有收錄的頂點，甚至你可以直接掃描所有的頂點，然後要找那個沒有收錄的，並且它的距離又是最小的那一個，於是這一步的時間複雜度就是O(V)數量級的，如果我們用這個簡單粗暴的方法去做一步的話呢，後面那個賦值語句就真的只是賦值語句，那就簡單了，因為我們所有的頂點都要被收錄一次，外循環是有V的，在每一個循環裡面，你要掃描一遍，又是一個O(V)的掃描，所以整體這一步的時間複雜度O(V^2)的，那麼在收集的過程中呢，要涉及到V的每個鄰接點，也就是每條邊又被訪問了一遍，所以這個也是跟E成正比的，對於稠密圖來說，稠密圖就是這個圖裡面有好多好多的邊，一般來說我們認為邊的條數跟頂點的個數O(V^2)這個數量級的，那這種情況下，整體的時間複雜度，就是O(V^2)數量級的，所以對於稠密圖來說效果還是比較好，關鍵是實現起來程序容易寫，另外一種方法，就是我怎樣能夠每次很快的找到一個最小的距離呢？那就用到了最小堆的知識，如果我把整個數組是存成一個最小堆的，每次我只要把堆的根節點彈出來，然後調整最小堆，所以每次獲得最小距離這一步操作是一個log(V)時間複雜度的演算法，比前面的O(V)要快多了，但是更新dist的值就變成了稍微複雜的事情，你不僅要把值更新，而且還要把它插回到最小堆里去，那麼這個過程也是O(logV)的過程，總體的時間複雜度呢，就變成了VlogV加上對於每一條邊的時間複雜度，ElogV，通常來說我們覺得邊的個數總比點的個數稍微多一點，至少是同一個數量級的，否則的話，整個圖都不連通了，所以我們可以把時間複雜度最後寫成是ElogV,如果是稀疏圖的話，怎麼理解稀疏圖呢?就是E跟V是同一個數量級的，它不是V^2數量級的，最後時間複雜度就是ElogV,比O(V^2)要好一點。

所以如果這個圖充分稀疏的話，用一個最小堆去實現Dijkstra會得到更好的效果。