交通地理与网络科学/迪杰斯特拉算法

概述

迪杰斯特拉算法是一种广泛使用的图搜索算法，它解决有非负边权重的图的单源最短路径问题，产生一个最短路径树。该算法由 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$ 中的每个节点执行。

该算法的更多细节可以在 中找到。