算法之「迪傑斯特拉(Dijkstra)算法」

最短路徑

生活中，我們常常會面臨著對路徑的最優選擇問題，可能是路程最短，也可能是時間最短，這個的最短路徑就類似路程最短的選擇。

比如在上海，乘地鐵去某個地方，上海的地鐵路線很多，從地圖上看上去就是一個網。去某個地方就會有多條路線的選擇，我們一般就會選最短那條路線。當然，在現實生活中，還會考慮時間、換乘等因素，這裡只是舉個例子說什麼是最短路徑。

地鐵換乘貌似一眼就可以看出來那條路線是最優的路線。但是在一些複雜的情況下，人眼就很難確定最優路線來，比如送外賣、自駕車等。人眼就很難做出最優選擇，因為路況等因素，根本沒法判斷。這時就需要用算法來選擇最佳路線了。這也是這篇文章的主角：迪傑斯特拉（Dijkstra）算法。

迪傑斯特拉算法

迪傑斯特拉（Dijkstra，又譯戴克斯特拉）算法由荷蘭計算機科學家艾茲赫爾·迪傑斯特拉在1956年提出。使用了廣度優先搜索解決帶權有向圖的單源最短路徑問題。通過一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑，產生一個最短路徑樹。

迪傑斯特拉算法步驟

1.標記所選的初始頂點，當前距離為 0，其餘頂點設為無窮大。
2.將具有最小當前距離的非訪問頂點設置為當前頂點 C。
3.對於當前頂點 C 的每個鄰居頂點 N：將當前距離 C 與連接 C—N 的邊緣的權重相加。 如果它小於頂點 N 的當前距離，則將其設置為 N 的新當前距離。
4.將當前頂點 C 標記為已訪問。
5.如果有非訪問頂點，重複步驟2，直到所有頂點均訪問。

迪傑斯特拉算法時間複雜度

假如我們有 V 表示圖中的頂點個數，E 表示圖中的邊個數。

如果用一個鍊表或者數組來存儲所有頂點的集合，要找到最短路徑算法所需的運行時間是 。

如果用鄰接表 + 二叉堆來用作優先隊列來查找最小的頂點，那麼算法所需的時間為

。

如果用鄰接表 + 斐波納契堆能稍微提高一些性能，讓算法運行時間達到 。

迪傑斯特拉算法示例

Dijkstra的算法是用來計算一個頂點（起始點）與圖中每個其他頂點之間的最短路徑。

搜索頂點 C 和圖中其他頂點之間的最短路徑。

首先我們需要初始化數據，選擇頂點 C 為初始頂點，當前距離為 0，對於其餘頂點，由於我們不知道最小距離，因此它開始為無窮大。

現在與 C 相鄰的頂點為 A、B、D，因為沒有特定的順序，我們選擇從 A 開始。由於 C 到 A 的權值為 1，當前頂點的最小距離加 C—A 的權值小於默認的無窮大，所以 C—A 的最小距離為 0+1=1。

由於 C 到 B 的權值為 7，當前頂點的最小距離加 C—B 的權值小於默認的無窮大，所以 C—B 的最小距離為 0+7=7。

由於 C 到 D 的權值為 2，當前頂點的最小距離加 C—D 的權值小於默認的無窮大，所以 C—D 的最小距離為 0+2=2。
此時 C—A 的最短距離為 1。
C—B 的最短距離為 7。
C—D 的最短距離為 2。

選取下一個當前頂點為 A，由於 A 到 B 的權值為 3，當前頂點的最小距離加 A—B 的權值小於 7，所以 C—B 的最小距離為 1+3=4。
當前的最短路徑分別為 C—A、C—A—B、C—D。

選取下一個當前頂點為 D，由於 D 到 E 的權值為 7，當前頂點的最小距離加 D—E 的權值小於無限大，所以 C—E 的最小距離為 2+7=9。
此時 D—B 的權值為 5，C—B 的最小距離為 2+5=7，大於當前的最小距離，因此不用更新 C—B 的距離。
當前的最短路徑分別為 C—A、C—A—B、C—D、C—D—E。

選取下一個當前頂點為 B，由於 B 到 E 的權值為 1，當前頂點的最小距離加 B—E 的權值小於 9，所以 C—E 的最小距離為 4+1=5。現在更新C—E 的最短距離為 5，所有頂點都以標記完成。

最後，最短距離分別為 C—A=1，C—B=4，C—D=2，C—E=5。
最短路徑分別為 C—A、C—A—B、C—D、C—A—B—E。

總結

迪傑斯特拉（Dijkstra）算法使用了廣度優先搜索解決帶權有向圖的單源最短路徑問題。通過一個頂點作為源節點然後找到該頂點到圖中所有其它節點的最短路徑。

用一個鍊表或者數組來做存儲的數據結構時，時間複雜度為 。

但通過對存儲結構的優化，用二叉堆或者斐波納契堆來存儲時，效率上有一定的提升。

THE END

更多精彩內容在路上，歡迎「掃碼」訂閱

我走得很慢，但不會後退；一直在路上，用心寫未來。