荷蘭資格最老的程序員告訴你，如何用短短20分鐘影響整個20世紀

保持對同一個問題的思考

在那一個瞬間找到了答案

一個既是貪心又是最優的最短路徑演算法

1

人們總是在做一件事情：

找最短路徑

公元前32世紀，蘇美爾人在粘土片上製作了城市地圖，圖上描繪了神廟、公園、城牆、河流。這幅地圖是世界上現存最古老的地圖。隨著人類的發展，地圖的形式越來越豐富，但其核心都是一致的，也就是幫助人們找到去某個地方的最短路徑。

蘇美爾人製作的地圖是世界上現存最古老的地圖

18世紀初，在普魯士的格尼斯堡，普瑞格爾河從市中心流過，河中心有兩座小島，島和兩岸之間建築有七座古橋。

哥尼斯堡的七座橋

當地居民有一項消遣活動，就是試圖每座橋恰好走過一遍並回到原出發點。這個問題俗稱七橋問題。有很多外地遊客慕名而來，躍躍欲試，但從來沒人成功過。

於是有人寫信給當時著名數學家歐拉，希望他能解決這個問題。歐拉通過簡化七橋問題為一個簡單圖形，證明了這種走法是不存在的。證明過程非常簡單，但不經意間他開創了一個新的學科：圖論。

時光輪轉，20世紀30年代，旅行商問題（Travelling salesman problem， 簡稱TSP）正式載入史冊：

「有一個旅行商人要拜訪n個城市，每個城市只能拜訪一次，而且最後要回到原來出發的城市。這位商人如何設計拜訪順序，使走過的路徑最短？ 」

雖然已經誕生了非常多的啟發式演算法和精確解法，但一直沒有出現能夠解決旅行商問題的有效演算法。旅行商問題的難度非常大，但是科學家們對它熱情不減，希望能找到更加高效的演算法。從誕生至今，它一直是優化領域最經常研究的問題之一。

TSP問題歷史悠久，最早的描述來自18世紀的騎士環遊問題（Knights Moves）

在歷史長河中，人們從各個角度致力於尋找最短路徑，然而只能做到將路徑的表示形式越來越簡單，卻沒有一個機械化演算法可以幫助人們快速尋找最短路徑。

直到1956年，Dijkstra演算法，一個為求最短路徑而生的演算法，它的誕生改變了這個局面。

2

在咖啡館誕生的

Dijkstra演算法

Dijkstra演算法的發明者，叫Edsger Wybe Dijkstra。

Dijkstra是荷蘭最早期的程序員，他提出了Go to 有害論（GOTO Statement Considered Harmful），認為只用三種基本控制結構可以寫各種程序（即順序結構、條件結構、循環結構）。這是結構化設計運動的開始，為全世界的程序員指明了方向。

故事要從1952年開始說起。當時Dijkstra剛完成學士學位，參加了劍橋大學開設的一個課程。在他的課程導師，也是著名的英國計算機科學家威爾克斯（Maurice Vincent Wilkes）推薦下，Dijkstra來到了荷蘭國家數學研究中心（Mathmetical Centre）。在荷蘭數學家阿德里安·范韋恩哈登（Aad van Wijngaarden）領導下開始了編程生涯，參與了新計算機的程序研發，包括ARRA I、ARRA II和ARMAC，開始研發荷蘭最早期的第一批計算機。

由於這些計算機還在設計當中，Dijkstra的工作實際上是為這些並不存在的機器寫程序，而且只能用紙和筆把程序寫出來，驗證它們的正確性，和負責硬體的同事確認需要的指令是可以被實現的，並寫出計算機的規範說明。因此後來他很習慣於不測試自己寫的程序，因為無法測試。

時間來到了1956年，Dijkstra從事編程工作到了第4個年頭，此時新計算機ARMAC已經研製完成，為了方便向媒體和公眾展示ARMAC的計算能力，Dijkstra需要想出一個可以讓不懂數學的媒體和公眾理解的問題，來驗證這台計算機的實力。Dijkstra思考許久，始終沒有一個合適的答案。

就在一個陽光明媚的下午，Dijkstra和未婚妻在一家咖啡館的陽台上喝咖啡，他習慣性地思考這個問題。

而此時Dijkstra的未婚妻並沒有察覺獃獃的Dijkstra，一個勁地跟Dijkstra聊起，準備出門去另一座城市拜訪貴族的事情。

Dijkstra突然間靈光一閃，如果讓計算機演示如何計算荷蘭兩個城市間的最短路徑，這樣問題和答案都容易被人理解。

Dijkstra也不管未婚妻的詢問，在沐浴在暖和的陽光下，埋頭想著自己的問題，終於在20分鐘內想出了一個簡潔且高效計算最短路徑的方法，也就是我們所熟知的Dijkstra演算法。

但當時卻沒有任何一個期刊關注計算領域，於是Dijkstra沒有馬上發表。直到3年後的1959年，這個演算法才正式發表在Numerische Mathematik創刊號上。

1972年他獲得了圖靈獎，獲獎原因之一，就是因為他提出了Dijkstra演算法（圖靈獎素有計算機界的諾貝爾獎之稱）。

當然，這個演算法僅僅是Dijkstra初試身手的處女作。他是一位高產的作家，一生中寫了 1300 多篇文章。他用自己姓名的首字母 EWD 給他的文章編號：EWD 1，EWD 2，…EWD 1318。在計算機科學界，這些文章被稱為EWD報告（EWD的文章地址：http://www.cs.utexas.edu/users/EWD/）。曾在1994 年時有人對約 1000 名計算機科學家進行了問卷調查，選出了 38 篇這個領域最有影響力的論文，其中有5篇來自Dijkstra。

Edsger Wybe Dijkstra

3

Dijkstra演算法

是一個既貪心又最優的演算法

大名鼎鼎的Dijkstra演算法是怎麼工作的？

設兩個集合，S和U。初始狀態下，S只包含源點v，即：S＝{v}，U包含除v外的其他頂點，即：U={其餘頂點}。

設dis[u]表示源點v到u的最短距離，若v與U中頂點u有邊，則dis[u] = d(v,u)（d(v,u)表示v到u這條邊的長度），否則dis[u] = ∞。

第一步，從U中選取一個距離源點v最小的頂點k，即dis[k]最小，把k加入S中，同時在U中剔除k。

第二步，以k為中間點，修改源點v與U中各頂點的距離。若從源點v經過頂點k到頂點u的距離，比原來的dis[u]小（dis[k] + d(k,u) < dis[u]），則更新dis[u]。

第三步，重複第一步和第二步，直至S包含所有頂點，演算法結束。

事實上，Dijkstra演算法思想非常簡潔：

Dijkstra演算法對圖中的頂點分成兩類，一類是已經求出最短路徑的頂點集合，用S表示，初始時在S中的只有源點。另一類是其餘為未確定最短路徑的頂點集合，用U表示。

Dijkstra演算法不斷在U中挑出與源點距離最短的頂點，加入S中，同時每挑出一個頂點，則利用這個頂點的信息更新U中所有頂點與源點的距離數值。

這種演算法有種貪心演算法的意味：總是做出在當前看來最好的選擇，看似不從整體的角度上考慮，不可能得到最優解。

實際上，Dijkstra演算法能夠得到最優解，其正確性已被確認，兼具快速和最優的特性。

Dijkstra演算法之所以能做到簡潔，還有一個重要原因是Dijkstra當時在咖啡館裡沒有紙和筆，這強迫他在思考時避免複雜度，儘可能追求簡單。

以Dijkstra演算法尋找頂點a與頂點b之間的最短路徑

4

實際上到處都有

Dijkstra演算法的影子

儘管後來有很多新的演算法誕生，比如Floyd，SFPA，但是Dijkstra演算法因其性能的穩定性，依然在現代得到廣泛應用。

互聯網時代，網路成為了繼水電煤後第四個重要的生存資源。保證網路信號的正常，是一項難度很大的工作。網路信號的傳輸要經過非常多的中間節點，才能達到目的地。而網路信號的傳輸速度，取決於當中的路由演算法。路由演算法的性能必須要好，才能以最快的路徑傳輸信息。

值得注意的是，Dijkstra是現代常用的路由演算法。

信號傳輸經過多個節點，必須使用演算法計算最短的傳輸路徑

再試想一下，如果現在若是沒有導航軟體，估計就連不是節假日都可能堵在路上。特別是遇到高速公路分叉的地方，走錯一個都要多耽誤半個小時甚至一個小時。

當然，即使有導航軟體，現在數據越來越多，可以獲知路上哪裡發生堵塞、封路、事故，對導航軟體的計算要求也越來越高，需要穩定快速的演算法來幫助導航軟體規划到目的地的最優路徑。值得注意的是，從GPS導航誕生開始，Dijkstra演算法一直是常用的導航演算法。

大到物流路徑的規劃、大型作業的關鍵路徑計算、小到微型晶元的電路排布、DNA合成都需要計算最短路徑，可以說最短路徑的計算無處不在，Dijkstra演算法則是解決這類問題的熱門方案。

5

發現生活中的答案

「生活中從不缺少答案，而是缺少發現答案的眼睛」。

砸到牛頓的蘋果，引發了關於萬有引力理論的思考。愛因斯坦看到一束光線，沉思如何追一束光，萌發了狹義相對論的框架。Dijkstra在咖啡館的20分鐘思考，成就了Dijkstra演算法，一生中最著名的成就之一。

偶然的突發事件，可能帶給你新的靈感，而這些新的靈感，也許為你思考已久的問題帶來新的思路。看似短暫的瞬間，誕生如此深刻的理解，事實上，這是他們保持對同一問題的長期思考，才能在那一瞬間，得到了自己的答案。

本文系網易新聞·網易號「各有態度」特色內容

部分資料來源於網路

轉載請在公眾號中，回復「轉載」

-----這裡是數學思維的聚集地------

「超級數學建模」（微信號supermodeling），每天學一點小知識，輕鬆了解各種思維，做個好玩的理性派。50萬數學精英都在關注！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！