戴克斯特拉演算法

戴克斯特拉演算法，又稱迪傑斯特拉演算法、Dijkstra演算法，是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉在1956年發現的演算法，並於3年後在期刊上發表。戴克斯特拉演算法使用類似廣度優先搜尋的方法解決賦權圖的單源最短路徑問題。該演算法存在很多變體：戴克斯特拉的原始版本僅適用於找到兩個頂點之間的最短路徑，後來更常見的變體固定了一個頂點作為源結點然後找到該頂點到圖中所有其它結點的最短路徑，產生一個最短路徑樹。該演算法解決了圖 formula_1上帶權的單源最短路徑問題:196–206。具體來說，戴克斯特拉演算法設定了一頂點集合formula_2，在集合formula_2中所有的頂點與源點formula_4之間的最終最短路徑權值均已確定。演算法反覆選擇最短路徑估計最小的點formula_5並將formula_6加入formula_2中。該演算法常用於路由演算法或者作為其他圖演算法的一個子模組。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示城市間開車行經的距離，該演演算法可以用來找到兩個城市之間的最短路徑。應當注意，絕大多數的戴克斯特拉演算法不能有效處理帶有負權邊的圖。戴克斯特拉演算法在計算機科學的人工智慧等領域也被稱為均一開銷搜尋，並被認為是的一個特例。演算法描述.戴克斯特拉演算法透過保留目前為止所找到的每個頂點formula_8從formula_4到formula_10的最短路徑來工作。初始時，原點formula_4的路徑權重被賦為 0 。同時把所有其他頂點的路徑長度設為無窮大，即表示我們不知道任何通向這些頂點的路徑。當演算法結束時，formula_12 中儲存的便是從formula_4到formula_10的最短路徑，或者如果路徑不存在的話是無窮大。鬆弛操作是戴克斯特拉演算法的基礎操作：如果存在一條從formula_6到formula_10的邊，那麼從formula_4到formula_10的一條新路徑是將邊formula_19新增到從formula_4到formula_6的路徑尾部來拓展一條從formula_4到formula_10的路徑。這條路徑的長度是formula_24。如果這個值比目前已知的formula_12的值要小，那麼可以用這個值來替代當前formula_12中的值。鬆弛邊的操作一直執行到所有的formula_12都代表從formula_4到formula_10的最短路徑的長度值。演算法維護兩個頂點集合formula_2和formula_31。集合formula_2保留所有已知實際最短路徑值的頂點，而集合formula_31則保留其他所有頂點。集合formula_2初始狀態為空，而後每一步都有一個頂點從formula_31移動到formula_2。這個被選擇的頂點是formula_31中擁有最小的formula_38值的頂點。當一個頂點formula_6從formula_31中轉移到了formula_2中，演算法對formula_6的每條外接邊formula_43進行鬆弛。《演算法導論》中給出了以下虛擬碼：該虛擬碼計算並保留圖formula_44中原點formula_4到每一頂點formula_10的最短距離formula_12。其中，函式formula_48將頂點集合formula_31中有最小formula_38值的頂點formula_6從formula_31中刪除並返回formula_6。1 function Dijkstra(G, w, s)2   INITIALIZE-SINGLE-SOURCE(G, s) //實際上的操作是將每個除原點外的頂點的formula_12置為無窮大，formula_553   formula_564   formula_57                 //formula_31是頂點formula_59的一個優先佇列，以頂點的最短路徑估計排序5   while(formula_60)6       do formula_61 //選取formula_6為formula_31中最短路徑估計最小的頂點7 formula_648 for each vertex v formula_659           do RELAX(u, v, w)       //鬆弛成功的結點會被加入到佇列中如果我們只對在formula_4和formula_67之間尋找一條最短路徑的話，我們可以在第5或第6行新增條件如果滿足formula_68的話終止程式。在肯尼·羅森所著的《離散數學及其應用》中給出瞭如下的另一份虛擬碼：1 procedure Dijkstra(G：邊全為正權的圖）3    for formula_71 to n4       formula_725    formula_736    formula_747    while formula_758    begin9      formula_76不屬於formula_2的formula_78最小的一個頂點10        formula_7911        for 所有不屬於formula_2的頂點formula_1012            if formula_82 then formula_83時間複雜度.我們可以用大O符號將該演算法的執行時間表示為邊數formula_85和頂點數formula_86的函式。對於任何基於頂點集formula_31的實現，演算法的執行時間是formula_88，其中formula_89和formula_90分別表示完成鍵的降序排列時間和從formula_31中提取最小鍵值的時間。對於沒有任何最佳化的戴克斯特拉演算法，實際上等價於每次遍歷了整個圖的所有結點來找到Q中滿足條件的元素，此外實際上還需要遍歷所有的邊一遍，因此演算法的複雜度是formula_93。對於邊數少於formula_94的稀疏圖來說，可以用鄰接表來更有效的實現該演算法。可以使用一個二叉堆或者斐波納契堆用作優先佇列來尋找最小的頂點以最佳化演算法。當用到二叉堆的時候，演算法所需的時間為formula_96，斐波納契堆能提高一些效能，讓演算法執行時間達到formula_97。然而，使用斐波納契堆進行程式設計，有時會由於演算法常數過大而導致速度沒有顯著提高。下面是一些戴克斯特拉演算法經典實現的複雜度比較：演算法正確性證明.戴克斯特拉本人在他的論文中給出了一份簡單的證明。《演算法導論》使用迴圈不變式給出瞭如下的一份證明：已知一帶權圖formula_98，其加權函式formula_99的值非負，源點為formula_4。對該圖執行戴克斯特拉演算法，對所有formula_101有formula_102。其中formula_38表示u點的最短路徑估計，formula_104表示formula_4到formula_6點的最短路徑。證明：證明如下的迴圈不變式成立即可：在每次執行EXTRACT-MIN時，對每個頂點formula_107，有formula_102成立即可。由於上界性質，在formula_6加入了formula_2之後，一旦有formula_102，則在後面的每次迴圈中都不會改變這個性質。初始化：第一次迴圈前，formula_112，因此迴圈不變式顯然成立。保持：實際上要證明每一輪迴圈中加入到formula_2中的結點滿足formula_102。利用反證法，假設formula_6是第一個不滿足此條件的結點，考慮迴圈開始前的狀況，首先formula_6一定不等於formula_4，這是顯然的。其次formula_4一定有到formula_6的路徑，否則路徑為無窮大。那麼假設在formula_6進入時，有最短路徑formula_121，假設該路徑上存在兩個點formula_122，formula_123。formula_124、formula_125，且x是y的前驅，路徑formula_126可以分解為formula_127，其中路徑formula_129和路徑formula_131可以為空。由於formula_6是第一個不滿足formula_102的，又因為formula_122是滿足該條件的，而且formula_135一定已經被鬆弛過了，所以formula_123是滿足該條件的。現在只需要推出矛盾，即可證明u不存在：formula_123在formula_6之前出現，而且圖中所有權值非負，因此有formula_139，所以：formula_140，但是由於formula_6和formula_123同時在formula_143中，因此formula_144，因此必有formula_145，也就證明了formula_6點不可能不滿足該條件，上述假設為假，原命題得證。終止：終止時，formula_147，由於formula_148，因此formula_149，因此對所有formula_101有formula_102。演算法起源與歷史.從鹿特丹到格羅寧根的最短路徑是什麼？實際上，這就是對於任意兩座城市之間的最短路問題。解決這個問題實際上大概只花了我20分鐘：一天早上，我和我的未婚妻在阿姆斯特丹購物，累了，我們便坐在咖啡館的露臺上喝咖啡，然後我就試了一下能否用一個演算法解決最短路問題。正如我所說，這是一個20分鐘的發現。不過實際上，我在3年後的1959年才把這個演算法發表在論文上。即使現在來看這篇論文的可讀性也非常高，這個演算法之所以如此優雅，其中一個原因就是我沒用筆紙就設計了它。後來我才知道，沒用筆紙設計的優點之一是你不得不避免所有可避免的複雜問題。令我驚訝的是，這個演算法最終成為我成名的基石之一。戴克斯特拉1956年在荷蘭數學和計算機科學研究學會擔任程式設計師時為了展示新型計算機ARMAC的功能曾思考過最短路徑問題的解法。他的目標是讓不去實際計算的人也能理解這個問題和解決的方法，於是他在發現了這個演算法之後在ARMAC上做了簡單實驗。1959年，他正式將此演算法發表在期刊上，該演算法也成為了戴克斯特拉成名的基石之一。演算法相關應用.中需要計算最短路時常常要用到該演算法，該演算法在開放最短路徑優先和中間系統到中間系統協議中的相關應用是其在網路路由中的典型實現。戴克斯特拉演算法及其改進演算法應用廣泛，尤其是在尋路、交通、規劃中。如果有已知資訊可用來估計某一點到目標點的距離，則可改用A*搜尋演算法，以減小最短路徑的搜尋範圍，戴克斯特拉演算法本身也可以看作是A*搜尋演算法的一個特例。戴克斯特拉演算法本身採用了與Prim演算法類似的貪心策略。快速行進演算法與戴克斯特拉演算法同樣有相似之處。參考源程式.以下是該演算法使用堆最佳化的一個C++實現參考：using namespace std;// iPair ==&gt; Integer Pairtypedef pair iPair;// 加邊void addEdge(vector  adj[], int u,int v, int wt)adj[u].push_back(make_pair(v, wt));adj[v].push_back(make_pair(u, wt));// 計算最短路void shortestPath(vector adj[], int V, int src)// 關於stl中的優先佇列如何實現，參考下方網址：// http://geeksquiz.com/implement-min-heap-using-stl/priority_queue pq;// 距離置為正無窮大vector dist(V, INF);vector visited(V, false);// 插入源點，距離為0pq.push(make_pair(0, src));dist[src] = 0;/* 迴圈直到優先佇列為空 */while (!pq.empty())// 每次從優先佇列中取出頂點事實上是這一輪最短路徑權值確定的點int u = pq.top().second;pq.pop();if (visited[u]) {continue;visited[u] = true;// 遍歷所有邊for (auto x : adj[u])// 得到頂點邊號以及邊權int v = x.first;int weight = x.second;//可以鬆弛if (dist[v] &gt; dist[u] + weight)// 鬆弛dist[v] = dist[u] + weight;pq.push(make_pair(dist[v], v));}// 列印最短路printf("Vertex Distance from Source\n");for (int i = 0; i 10} {}".format(d, c, n))def main():for i in range(1, vertices_number + 1):if str(i) not in dest:start.append(str(i))find_shortest_router()if __name__ == '__main__':main()參考.擴充套件閱讀.