迪傑斯特拉
(艾茲格·W·迪科斯徹) Edsger Wybe Dijkstra(1930年5月11日~2002年8月6日）
荷蘭計算機科學家，畢業就職於荷蘭Leiden大學，早年鑽研物理及數學，而後轉為計算學。曾在1972年獲得過素有計算機科學界的諾貝爾獎之稱的圖靈獎， 之後，他還獲得過1974年AFIPS Harry Goode Memorial Award、1989年ACM SIGCSE計算機科學教育教學傑出貢獻獎、以及2002年ACM PODC最具影響力論文獎。
 |
| 艾茲格·W·迪科斯徹 |
曾經提出“goto有害論”信號量和PV原語，解決了有趣的“哲學家聚餐”問題。於2002年8月6日在荷蘭Nuenen自己的家中與世長辭。終年72歲。
艾茲格·W·迪科斯徹在離散數學中的貢獻包括：
提出了目前離散數學套用廣泛的最短路徑算法(Dijkstra's Shortest Path First Algorithm)
迪傑斯特拉算法用於求解一個有向圖（也可以是無向圖，無向圖是有向圖的一種特例）的一個點（稱之為原點）到其餘各點（稱之為周邊點）的最短路徑問題。算法構思很是巧妙（我這么認為），簡直達到了“無心插柳柳成蔭”的境界。算法本身並不是按照我們的思維習慣——求解從原點到第一個點的最短路徑，再到第二個點的最短路徑，直至最後求解完成到第n個點的最短路徑，而是求解從原點出發的各有向路徑的從小到大的排列（如果這個有向圖中有環1-2-3-1算法豈不是永無終結之日了？？！！），但是算法最終確實得到了從原點到圖中其餘各點的最短路徑，可以說這是個副產品，對於算法的終結條件也應該以求得了原點到圖中其餘各點的最短路徑為宜。清楚了算法的這種巧妙構思後，理解算法本身就不是難題了。
算法把一個圖（G）中的點劃分成了若干部分：
1）：原點（v）；
2）：所有周邊點（C）；
另外有一個輔助集合S，從v到S中的點的最短路徑已經求得。S的最初狀態是空集。
這樣就可以進一步劃分圖（G）：
1）：原點（v）；
2）：已求出v至其最短路徑的周邊點（S）；
3）：尚未求出v至其最短路徑的周邊點（Other=C-S）；
算法的主體思想：
A、找到v——Other所有路徑中的的最短路徑vd=v——d（Other的一個元素）；
B、找到v——S——Other所有路徑中的的最短路徑vi=v——i（Other的一個元素）；
C、比較vd和vi如果vd<=vi則將d加入S且從Other中刪除，否則將i加入S且從Other中刪除。
重複以上步驟直至Other為空集。
我們求得的最短路徑是升序排列的，那為什麼下一條最短路徑就存在於v——Other或v——S——Other之中呢，難道不能存在於v——Other——Other之中嗎？？當然不能，因為假設是存在於v——Other——Other之中，那么肯定有一條比這條路徑更短的路徑v——Other我們沒找到呢！
<偽碼>
在下面的算法中,u:=Extract_Min(Q)在在頂點集Q中搜尋有最小的d【u】值的頂點u。這個頂點被從集合Q中刪除並返回給用戶。
1function Dijkstra(G, w, s)
2 for each vertex v in V【G】 // 初始化
3 d【v】 := infinity
4 previous【v】 := undefined
5 d【s】 := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijstra算法主體
9 u := Extract_Min(Q)
10 S := S union
11 for each edge (u,v) outgoing from u
12 if d【v】 > d【u】 + w(u,v)// 拓展邊(u,v)
13 d【v】 := d【u】 + w(u,v)
14 previous【v】 := u
如果我們只對在s和t之間尋找一條最短路徑的話，我們可以在第9行添加條件如果滿足u=t的話終止程式。
現在我們可以通過疊代來回溯出s到t的最短路徑
1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous【u】
現在序列S就是從s到t的最短路徑的頂點集.
<時間複雜度>
我們可以用大O符號將Dijkstra算法的運行時間表示為邊數m和頂點數n的函式。
Dijkstra算法最簡單的實現方法是用一個鍊表或者數組來存儲所有頂點的集合Q,所以搜尋Q中最小元素的運算(Extract-Min(Q))只需要線性搜尋Q中的所有元素。這樣的話算法的運行時間是O(n2)。
對於邊數少於n2的稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra算法。同時需要將一個二叉堆或者斐波納契堆用作優先佇列來尋找最小的頂點(Extract-Min)。當用到二叉堆的時候，算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓算法運行時間達到O(m + n log n)。
