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

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

我們按遞增，或者說如果有並列數字的話，非遞減，更嚴格的說，我們按照遞增的順序來找從某一個固定的頂點到各個其它頂點的最短路，這是什麼意思呢，我們看一個例子就清楚了，比如說我們有一個圖如上圖所示，然後我們的原點從V3出發，從這個點出發去找它到各個其它頂點的最短路，那我們說我們是按照遞增的順序找最短路的，這個問題的初始情況就是從一個路徑長度為0路徑開始，也就是說原點到它自己是不用走路的，所以它的路徑長度是0，

有了這個0以後，我們要開始往下生成下一組路徑，就是路徑長度為1的，哪些頂點會被收進來了呢？很顯然的，就是從這個原點直接有邊發出指到的，即V1,V6這兩個點，它們到原點的距離，顯然是1，要注意到它們兩個跟V3的關係是什麼，它們實際上是V3的直接的鄰接點，

下一步的頂點就是在上一步的基礎上再往外走一步，就是下一步的頂點了，所以很顯然的我們會看到跟原點距離為2的頂點是V2和V4,它們分別是V1出發，擴展一步得到的結果，從V6了是沒有了，因為它沒有邊發出去，所以我們再把V2和V4標記一下，這是路徑長度為2的兩個頂點，接下去，你就知道怎麼做了

到此為止，所有的頂點都已經訪問過了，我們的演算法就結束了，我們來回顧一下整個演算法的流程，你發現這些頂點是一個一個被收羅進來的，收羅的順序是從V3的直接鄰接點開始，然後一圈一圈往外擴展的，這是不是讓你想到一個老朋友呢？這個不就是廣度優先搜索嗎？事實上解決了這個問題，我們就解決了007要從孤島跳上岸，最少需要跳多少步，當然了，整個演算法要實現的時候，它不是說完全把BFS copy過來就可以了，我們還是要稍微做一點改動的。

首先我們來回顧一下上周我們講過的BFS，BFS要執行的話，先要有一個初始點，從這個初始點出發我說我已經訪問過它了(visited[S] = true;),然後把它壓到隊列里(Enqueue(S, Q)),然後就進入隊列的循環，每次從隊列里彈出一個結點(V = Dequeue(Q)), 然後去看一下它的每個鄰接點(for (V 的每個鄰接點W)),如果還沒有被訪問過，我就訪問它一下，再把它壓到隊列裡面(if (!visited[W]){visited[W] = true; Enqueue(W, Q);},整個這就是非常簡單的BFS的過程，

但是在我們這個要求最短路徑的演算法裡頭，其實visited這個東西是不需要的，所以我們在後面實現的時候，visited是要刪掉的，

但是於此同時，我們仍然需要另外的東西來讓我們判斷這個頂點有沒有被訪問過，是什麼東西呢？我們定義了另外一個數組，叫做dist,dist[W]定義的是從源點S到這個W它的最短距離，首先在程序一開始的時候，我可以把源點的距離定義為0，它自己到它自己的距離當然是0

其它的頂點，這個dist[W]初始化的時候應該怎麼定義呢？實際上，dist[W]起的很重要的作用除了記錄S到W的最短距離以外，它還當於一個visited, 與visited的作用是一樣的，在我們一開始它還沒有被訪問過的時候，我只要把它隨便定義成一個一看就知道不可能的數字，就可以了，就可以識別出來，不管它是無窮大，還是無窮小，還是-1，0行不行啊？這個問題你要想一下2333，總之我要把它定義為一個很特別的數，使得我一看到這個數就知道，這個dist還沒有被訪問過，如果它已經被訪問過的話，這應該是一個比較正常的距離值，那除此之外，你除了告訴007，你可以最少跳的步數是幾步之外，你還應該告訴他怎麼跳，所以我們還需要一個數組，來記錄它的路徑，這個數組是這樣定義的，對每一個頂點W，我是把從源點到W的路上一定要經過的某一個頂點，會存在這個path[W]裡面，那這是某頂點，到底是哪個頂點呢？我們一會再看

我們先來看一下，這個單源最短演算法取個名字叫Unweighted,就是無權的，輸入仍然是一個源點S,然後代碼是整個copy了BFS有用的部分，整個複製過來，

首先我們要做的就是把這個源點壓到隊列裡面(Enqueue(S, Q))，當然前提是，這個數組都已經被初始化好了，好了以後我們開始進入正題，我們先把源點壓進去，然後進入While循環，每次從裡面彈出一個頂點(V = Dequeue(Q)),當一個頂點被彈出來的時候，就意味著這個頂點到S的最短路已經被找到了，也就是dist[V]是已經被算好了的，算好了我才把它壓進去的，等它彈出來以後呢，我們就要往外擴展一步，也就是對V的每個鄰接點W,在這邊我要判斷是什麼呢，W有沒有被訪問過，那麼在我們這個問題裡頭，W如果沒有被訪問過，它一定是等於一個很奇特的值，比如說在這裡頭，我把它初始化為-1,

因為我們所有的距離如果都是正常的話，都得是個正數，所以-1說明肯定是沒有被訪問過的，如果它沒有被訪問過，我要訪問它，那麼在這個最短路裡頭，什麼叫訪問它呢？也就是我要把它這個距離更新一下，輪到計算它的距離了，它的距離是什麼呢？它的距離應該是它的前一個頂點，V的距離，然後再加1，所以dist[W]應該被更新為dist[V]加上1(dist[W] = dist[V] + 1)，在這個時候，W的最短距離就已經被找到了，那麼誰是S到W必經的頂點呢？就是它的前一個頂點V(path[W] = V),這樣記錄path這個數組，它會有什麼用呢？想一下，當我們整個程序完成了之後，比如說我指定了某個頂點W,要求你把從S到W的路徑列印出來，你要怎麼做呢？首先你去看一下這個path[W]等於多少，它等於的這個數一定是在他前面的那個頂點的編號，是個V,然後下一步你就要去看path[V]等於多少，path[V]的值就是訪問V之前的那一個頂點它的編號，於是你其實就可以順著path這個數組一個一個往前推，一直到你推到源點，你就得到了一個反向的路徑，是從W到S的路徑，那你怎麼能列印出從S到W的路徑呢？很簡單，你只要把你反向推的東西都壓到一個堆棧里，堆棧就是起反序作用的，堆棧是一個後進先出的結構，你只要沿著path把它一個一個頂點都壓到堆棧里，然後你再從S開始，把它一個一個pop出來，一邊pop一邊列印，你就得到了從S到W的一條路徑，接下來的問題就是整個這個演算法，它的時間複雜度是多少呢？當然我們在這裡要有一個假設，假設我們用的是一個鄰接表，就是用鏈表的方式去存的這個圖，所以V的每個鄰接點是很方便找到的，在這種情況下，整個演算法的時間複雜度是多少呢?其實如果真的按以前嵌套循環的方法去算時間複雜度，這個真的很難理解，while這個隊列不是空的時候，這個while循環到底會被執行多少次呢？這看上去不是很清楚，這個裡頭又套了一個for(V的每個鄰接點),這是什麼意思呢？其實你換個角度去理解，整個演算法的時間複雜度就變得很容易了，因為在整個演算法執行過程中，我們回想一下，每個頂點只Enqueue了一次，然後Dequeue了一次，所以整個執行的過程裡頭，實際上是涉及了兩倍的V,另外這個for循環是怎麼回事呢？(for V的每個鄰接點W),這個實際上就是把每條邊訪問了一次，所以整個演算法中間，每條邊被訪問了一次，所以我們演算法整體複雜度，就是O(|V|+|E|)