演算法基礎：最佳化演算法
|
學生不需要記住迪傑斯特拉最短路徑演算法的步驟。 |
迪傑斯特拉是一位荷蘭計算機科學家，他建立了最短路徑演算法。據說他只花了 20 分鐘就完成了。
智慧手機的眾多功能之一是能夠快速生成不同地點之間的路線。選擇標準各不相同，從最快到最短，通常包括步行、騎腳踏車、開車或乘坐公共交通工具。如果您偏離了原始路徑，手機將在幾秒鐘內為您重新規劃路線。一種有效找到最佳路線的方法是使用迪傑斯特拉演算法。這是一個最佳化演算法的示例。
地圖上有許多相互連線的位置，從任意一個位置開始，找到到達另一個位置的最短距離。所有位置都透過中間位置連線在一起，並且任何兩個連線位置之間的旅行時間是已知的。但是，並非所有位置都直接連線。
讓我們透過建立一個地圖的抽象來研究迪傑斯特拉的解決方案。
....... 地圖圖示 .......
首先，我們需要建立位置的地圖。我們將位置稱為節點。
....... 節點圖示 ......
兩個節點之間的距離（或取決於問題的行駛時間）稱為頂點（複數為頂點）。
...... 節點和頂點圖示 .....
首先，建立抽象，並新增如上所示的節點和標記的頂點。然後識別起點節點。識別與起點節點直接連線的每個節點，並將起點節點到該節點的距離分配給它。（這些是在下面連結示例中表示節點的圓圈中寫入的數字）所有頂點都塗成綠色。綠色頂點可能是最短路線的一部分。
接下來，識別包含最小數字的節點。識別與該節點連線的節點，並計算從起點到這些新節點的頂點的總和（並在節點中寫入）。如果這些節點中的一個已經具有一個比新計算的數字更大的值，則將其劃掉並替換為較小的數字。已新增到節點的頂點塗成綠色。如果這些節點中的一個具有一個值，該值小於或等於新計算的數字，則忽略它。
然後重複此過程。即識別新的最小節點，識別所有直接連線的節點，並計算總距離。屬於新的最短距離的頂點塗成綠色。最終，包含最小值的節點是我們試圖到達的節點。其中的值是起點和終點節點之間的最短距離。
連線它們的路徑是它們之間的綠色路徑
此動畫將幫助您瞭解此過程。
http://www.gitta.info/Accessibiliti/en/html/Dijkstra_learningObject2.html
雖然迪傑斯特拉演算法旨在找到兩點之間的最短距離，但最終網路具有從起點到網路中任何點的最短距離。
如果動畫中的網路有另一個節點距離起點超過 12 個單位，則它顯然不涉及最短路徑，但演算法將執行，直到所有可能的節點和路徑都被考慮。如果此問題在導航裝置中未解決，它將在找到從倫敦到伯明翰的最佳路線之前考慮蘇格蘭的道路。這顯然是浪費時間。對迪傑斯特拉演算法的簡單改進是在所有未考慮的頂點等於或大於起點和所需終點之間計算的最短距離時停止。
