Dijkstra algorithm：戴克斯特拉最短路徑算法

Home >> Blog >> Dijkstra algorithm：戴克斯特拉最短路徑算法

Dijkstra algorithm：戴克斯特拉最短路徑算法

荷蘭計算機科學家Edsger Dijkstra在 1959年提出了一種可以應用於加權圖的算法。該圖可以是有向的，也可以是無向的，條件是圖需要在其每條邊上包含一個非負值。他以他的名字將該算法命名為“Dijkstra 算法”。

讓我們直接進入文章，我們將學習以下幾項重點:

圖簡介

1. 什麼是 Dijkstra 算法？
2. 如何實現 Dijkstra 算法？
3. Dijkstra 算法的工作示例
4. Dijkstra 算法的應用
5. Dijkstra 算法的優缺點

在系列文章中，我們特別注重詳細的研究，基於圖，即"群論 G,* "和知識圖譜，這個文章將有助於我們的知識更上一層樓。

圖簡介

簡而言之，圖是用於描述幾個元素之間的連接的數據結構，這些元素稱為節點（或頂點），通常實時對象、人或實體以及節點之間的連接稱為邊。此外，兩個節點只有在它們之間存在邊時才會連接。

“圖本質上是由邊連接的節點/頂點的相互關係。”

通常，圖表適用於現實世界的應用，例如圖表可用於說明交通系統/網絡，其中節點表示傳輸或獲取產品的設施，邊表示連接節點的路線。

圖表可以分為兩部分；

• 無向圖：對於每對關聯的節點，如果一個人可以在兩個方向上從一個節點移動到另一個節點，則該圖稱為無向圖。
• 有向圖：對於每對關聯的圖，如果一個人可以在特定（單個）方向上從一個節點移動到另一個節點，則該圖稱為有向圖。在這種情況下，為了表示有向邊，實現了箭頭而不是簡單的線。

加權圖

權重圖是圖的邊緣具有“權重”或“成本”的圖，並且權重可以反映距離、時間、金錢或任何在它連結的幾個節點中顯示“關聯”的東西。這些權重是 Dijkstra 算法的基本要素。

什麼是 Dijkstra 算法？

如果為您提供了一個節點圖，其中每個節點都連結到具有不同距離的其他幾個節點，該怎麼辦。現在，如果您從圖中的一個節點開始，到圖中每個其他節點的最短路徑是什麼？

簡單解釋，用於在加權圖中找到從起始節點到目標節點的最短距離或路徑的算法稱為 Dijkstra 算法。

該算法生成從起始節點（源節點）到圖中所有其他節點（點）的最短路徑樹。

Dijkstra 算法利用邊的權重來尋找使源節點和所有其他節點之間的總距離（權重）最小的路徑。該算法也稱為單源最短路徑算法。

運用在SEO優化過程中，於初期客戶網站分析過程中即可以使用Dijkstra 算法來推算要到達第一頁的最短路徑，以減少客戶等待時間進而增加轉換率。

Dijkstra 算法是迭代算法過程，為我們提供從一個特定起始節點到圖的所有其他節點的最短路徑。它與最小生成樹不同，因為兩個頂點之間的最短距離可能不會涉及到圖的所有頂點。

需要注意的是，Dijkstra 算法僅適用於所有權重為正的情況，因為在執行過程中，邊的權重被添加以找到最短路徑。

因此，如果在圖的邊緣引入任何權重為負，則該算法將永遠無法正常工作。但是，在這種情況下可以使用一些算法，例如Bellman-Ford 算法。

眾所周知，廣度優先搜索(BFS) 可用於計算未加權圖的最短路徑，或者用於在所有邊上具有相同成本的加權圖。

但是，如果加權圖在其所有邊的成本不相等，則 BFS 會推斷出統一成本搜索。怎麼辦？

統一成本搜索不是按照從根開始的深度順序擴展節點，而是按照從根開始的成本順序來開發節點。該算法的一個變體被接受為 Dijkstra 算法。

通常，Dijkstra 算法的工作原理是鬆弛原理，其中精確距離的近似值被更合適的值穩定地置換，直到達到最短距離。

此外，到每個節點的估計距離始終是真實距離的高值，並且通常用最近確定的路徑的距離替換其先前值中的最小值。

它使用優先級隊列貪婪地選擇尚未訪問的最近節點，並在其所有邊上執行鬆弛過程。（來自）

涉及的示例

例如，一個人想要計算源 A 和目標 D 之間的最短距離，同時計算一個子路徑，該子路徑也是其源和目標之間的最短路徑。讓我們在這裡看看 Dijkstra 的算法是如何工作的；

它適用於這樣一個事實，即任何子路徑，假設頂點 A 和 D 之間的最短路徑的子路徑 B 到 D 也是頂點 B 和 D 之間的最短路徑，即每個子路徑都是最短路徑。

在這裡，Dijkstra 的算法在相反的方向使用此屬性，這意味著，在確定距離時，我們高估了每個頂點到起始頂點的距離，然後檢查每個節點及其鄰居以檢測到這些鄰居的最短子路徑。

這樣，算法通過搜索下一個合理的解決方案來部署貪婪方法，並期望最終結果將是整個問題的適當解決方案。

如何實現 Dijkstra 算法？

在逐步實現算法之前，讓我們考慮一下 Dijkstra 算法的一些基本特徵；

• 基本上，Dijkstra 算法從要選擇的節點開始，即源節點，它檢查整個圖以確定該節點與圖中所有其他節點之間的最短路徑。
• 該算法維護當前識別的從每個節點到源代碼的最短距離的軌跡，如果它識別出另一條最短路徑，則更新這些值。
• 一旦算法確定了源代碼中到另一個節點的最短路徑，該節點就會被標記為“已訪問”並且可以添加到路徑中。
• 這個過程一直持續到圖形中的所有節點都已添加到路徑中，這樣就創建了一條路徑，該路徑將源節點連接到遵循合理最短路徑的所有其他節點以到達每個節點。

現在解釋算法實現的逐步過程；

1. 第一步是將所有節點標記為未訪問，
2. 將選取的起始節點標記為當前距離為 0，其餘節點標記為無窮大，
3. 現在，將起始節點固定為當前節點，
4. 對於當前節點，分析其所有未訪問的鄰居，並通過將當前節點的當前距離與連接鄰居節點和當前節點的邊的權重相加來測量它們的距離，
5. 將最近測量的距離與分配給相鄰節點的當前距離進行比較，並將其作為相鄰節點的新當前距離，
6. 之後，考慮當前節點的所有未訪問鄰居，將當前節點標記為已訪問，
7. 如果目標節點已被標記為已訪問，則停止，算法結束，並且
8. 否則，選擇距離最小的未訪問節點，將其固定為新的當前節點，並從步驟 4 開始再次重複該過程。

Dijkstra 算法的工作示例

在上面的部分中，您已經逐步了解了 Dijkstra 算法的過程，現在讓我們通過一個解釋的示例來研究該算法。

我們將計算節點 C 和圖中其他節點之間的最短路徑。

1.在算法執行期間，每個節點將被標記為與節點 C 的最小距離，因為我們選擇了節點 C。

在這種情況下，節點C的最小距離為0。另外，對於其餘節點，由於我們不知道這個距離，它們將被標記為無窮大（∞），除了節點C（當前標記為紅點）。

2. 現在將檢查節點 C 的鄰居，即節點 A、B 和 D。我們從 B 開始，這裡我們將當前節點 (0) 的最小距離與連接該節點的邊 (7) 的權重相加節點 C 到節點 B 並得到 0+ 7= 7。

現在，該值將與 B 的最小距離（無窮大）進行比較，最小值是保持 B 的最小距離的那個，在這種情況下，7 小於無窮大，並將最小值標記到節點 B .

3. 現在，用鄰居 A 檢查相同的過程。我們將 0 與 1（將節點 C 連接到 A 的邊的權重）相加，得到 1。再次將 1 與 A 的最小距離（無窮大）進行比較，並標記最低值。

對節點 D 重複相同的操作，並將 2 標記為 D 處的最小值。

由於節點 C 的所有鄰居都已檢查，因此節點 C 用綠色複選標記標記為已訪問。

4. 現在，我們將選擇新的當前節點，使得該節點必須以最小的最小距離未被訪問，或者俱有最小編號且沒有復選標記的節點。這裡，節點 A 是最小距離為 1 的未訪問節點，用紅點標記為當前節點。

我們重複該算法，檢查當前節點的鄰居，同時忽略訪問節點，因此只檢查節點 B。

對於節點B，我們將1和3（連接節點A到B的邊的權重）相加得到4。這個值4，將與B的最小距離7進行比較，並將B處的最小值標記為4 .

5. 在此之後，節點 A 用綠色複選標記標記為已訪問。當前節點被選為節點D，它是未訪問過的，最近距離最小。我們重複該算法並檢查節點 B 和 E。

對於節點 B，我們將 2 加到 5，得到 7 並與 B 的最小距離值進行比較，因為 7>4，所以將節點 B 處的最小距離值保留為 4。

對於節點E，我們得到2+ 7= 9，並將其與E的最小距離為無窮大，並將最小值標記為節點E為9。節點D用綠色複選標記標記為已訪問。

6. 當前節點設置為節點B，這裡我們只需要檢查節點E，因為它未被訪問，而節點D被訪問。我們得到4+ 1=5，將其與節點的最小距離進行比較。

當 9 > 5 時，將節點 E 處的最小值保留為 5。

我們用綠色複選標記將 D 標記為已訪問節點，並將節點 E 設置為當前節點。

7. 由於它沒有任何未訪問的鄰居，因此不需要檢查任何內容。節點 E 用綠色標記標記為已訪問節點。

所以，我們完成了，因為沒有未訪問的節點。每個節點的最小距離現在表示該節點與節點 C 的最小距離。

Dijkstra 算法的應用

在學習任何算法之前，我們應該知道使用可以在實際應用中幫助我們的算法的基本目的。例如，對於 Dijkstra 算法，我們試圖找到基於最小路徑問題的解決方案。

例如，如果一個人想從城市 A 到城市 B，兩個城市都有不同的路線連接。他/她一般應該選擇哪條路線？

毫無疑問，我們會選擇用最少的時間、距離甚至成本到達目的地的路線。

此外，通過討論，它具有各種實際用例，其中一些應用程序如下：

• 對於地圖應用程序，它被廣泛用於測量兩個地理區域（如穀歌地圖）中的最短距離和檢查方向、發現指向圖形頂點的地圖位置、計算流量和延遲時間等。
• 對於電話網絡，這也廣泛應用於網絡和電信領域中的數據傳輸，以減少傳輸發生的障礙。
• 無論在機器人、運輸、嵌入式系統、實驗室或生產工廠等領域，只要解決最短路徑解釋的需求，就會應用該算法。
• 除此之外，其他應用還有道路狀況、道路封閉和施工，以及檢測開放最短路徑優先的 IP 路由。

Dijkstra 算法的優缺點

討論Dijkstra算法的一些優點；

1. 它的主要優點之一是它幾乎是線性的幾乎沒有復雜性。
2. 它可用於計算單個節點到所有其他節點和單個源節點到單個目標節點之間的最短路徑，方法是在目標節點達到最短距離後停止算法。
3. 它僅適用於有向加權圖，並且所有邊都應具有非負值。

儘管有各種應用和優點，但 Dijkstra 的算法也有缺點，例如：

1. 它進行了一項模糊的探索，在處理時會消耗大量時間，
2. 它無法處理負邊緣，
3. 由於它走向無環圖，因此無法獲得準確的最短路徑，並且
4. 此外，還需要保持對已訪問過的頂點的跟踪。

結論

其中，我們討論了用於查找最短路徑的 Dijkstra 算法，但是，在 Internet 上實現該算法的障礙之一是提供圖形的完整表示來執行該算法，因為單個路由器具有完整的輪廓對於互聯網上的所有路由器。我們已經看到

• 圖表用於顯示對象、實體或人之間的聯繫，它們具有主要元素：節點和邊。
• Dijkstra 算法能夠確定圖中一個選定節點和每個其他節點之間的最短路徑。
• 最後，部署 Dijkstra 算法所涉及的步驟。

希望你喜歡閱讀這篇文章並發現它很有用，對於其他類似的文章和不斷的學習，請定期關注我們。