交通地理與網路科學/迪傑斯特拉演算法

概述

迪傑斯特拉演算法是一種廣泛使用的圖搜尋演算法，它解決有非負邊權重的圖的單源最短路徑問題，產生一個最短路徑樹。該演算法由 Edsger W. Dijkstra 於 1956 年開發，適用於有向圖和無向圖。它常用於路由，以及其他需要在加權圖中查詢節點間最短路徑的應用。

有向圖的迪傑斯特拉演算法

對於前面定義的有向圖 $G$，迪傑斯特拉演算法可用於計算從源節點 $r$ 到網路中其他每個節點的最短（旅行時間）路徑。令 $\Delta$ 為 $G$ 的距離矩陣，其中 $\Delta _{ij}$ 表示從節點 $i$ 到節點 $j$ 的連結的長度（旅行時間）。如果節點 $i$ 和 $j$ 不相連，則 $\Delta$ 中的對應元素是一個非常大的數字。

令節點集$N$ 被分成兩個子集：$\Omega _{r}$ 和 $\Gamma _{r}$。 $\Omega _{r}$ 表示從 $r$ 出發的最短路徑已知的節點集，而 $\Gamma _{r}$ 是 $\Omega _{r}$ 的補集。令 $\Pi _{r}$ 表示 $\Omega _{r}$ 中節點的永久標籤向量。節點的永久標籤是從原點節點 $r$ 出發的最短距離。令 $\Phi _{r}$ 是 $\Omega _{r}$ 中節點沿最短路徑相鄰的節點集。令 $\Lambda$ 是 $\Gamma _{r}$ 中節點的臨時標籤向量。以下步驟解釋了演算法

• 初始化： 設定 $\Omega _{r}={r},\Pi _{r}={0},\Phi _{r}={0}$，並將一個大數分配給 $\Lambda$ 的所有元素。
• 節點探索： 查詢與任何父節點 $j$ 相鄰的所有子節點，這些子節點不在 $\Omega _{r}$ 中，使用距離矩陣 $\Delta$。計算每個子節點 $i$ 的臨時標籤，方法是將父節點 $j$ 從向量 $\Pi _{r}$ 中的永久標籤與連結長度 $i\rightarrow j:\Delta _{ij}$ 相加。
• 節點選擇： 選擇具有最小臨時標籤的節點，並將其新增到集合 $\Omega _{r}$ 的末尾，並將其從 $\Gamma _{r}$ 中刪除。將相應的父節點 $j$ 新增到集合 $\Phi _{r}$ 的末尾，並將相應的臨時標籤新增到 $\Pi _{r}$。使用更新後的 $\Omega _{r}$，重複步驟 2 和 3，直到 $\Gamma _{r}$ 中沒有元素。

要獲得從起點節點 $r$ 到網路中任何其他節點的最短路徑長度，請找到目標節點在 $\Omega _{r}$ 中的位置，並讀取 $\Pi _{r}$ 中對應位置的元素。要獲得最短路徑本身，請找到目標節點 $s$ 在 $\Omega _{r}$ 中的位置，讀取 $\Phi _{r}$ 中相同位置的元素，並重復此過程，直到在 $\Phi _{r}$ 中到達節點 $r$ 為止（即，反向跟蹤最短路徑直到到達起點）。以這種方式計算出的從起點節點 $r$ 到目標節點 $s$ 的最短路徑上的連結被分配到一個集合 $K_{rs}$ 中。

上述演算法針對單個起點節點 $r$ 執行，但為了獲得從每個節點到每個其他節點的最短路徑，以便進行出行分配和交通分配，Dijkstra 演算法應該針對圖 $G$ 中的每個節點執行。

該演算法的更多細節可以在 中找到。