迪杰斯特拉算法计算图中的最短路径

定义

迪杰斯特拉算法查找从特定节点（称为源节点）到连接图中所有其他节点的最短路径。它生成一个以源节点为根的最短路径树。它广泛用于计算机网络中，目的是生成最佳路由以最大限度地降低路由成本。

迪杰斯特拉算法

输入 - 表示网络的图；和一个源节点 s

输出 - 一个最短路径树 spt[]，以 s 作为根节点。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

初始化 -

大小为 **|V|**（节点数）的距离数组 **dist[]**，其中 **dist[s]** = **0** 且 **dist[u]** = ∞（无限），其中 u 表示图中除 s 之外的节点。
一个数组 **Q**，包含图中的所有节点。当算法运行完成时，**Q** 将变为空。
一个空集 **S**，将访问过的节点添加到其中。当算法运行完成时，**S** 将包含图中的所有节点。
当 **Q** 不为空时重复 -
- 从 **Q** 中移除具有最小 **dist[u]** 值且不在 S 中的节点 u。在第一次运行中，移除 **dist[s]**。
- 将 u 添加到 S，标记 u 为已访问。
- 对于每个与 u 相邻的节点 v，更新 dist[v] 为 -
  - 如果 (**dist[u]** **+ u-v 边权重**) **< dist[v]**，则
    - 更新 **dist[v] = dist[u] + u-v 边权重**
数组 **dist[]** 包含从 s 到每个其他节点的最短路径。

示例

可以使用示例最好地理解算法的工作原理。考虑以下图，其节点标记为 A 到 G，由带权边连接如下：

初始化如下：

dist[7]={0,∞,∞,∞,∞,∞,∞}
Q={A,B,C,D,E,F,G}
S = ∅

**第一轮** - 我们从 **Q** 中选择节点 **A**，因为它具有最低的 **dist[]** 值 **0**，并将其放入 S。A 的相邻节点是 B 和 C。我们根据算法更新对应于 B 和 C 的 dist[] 值。因此，数据结构的值变为：

dist[7]={0,5,6,∞,∞,∞,∞}
Q={B,C,D,E,F,G}
S={A}

此轮后的距离和最短路径如下图所示。绿色节点表示已添加到 S 的节点：

**第二轮** - 我们从 **Q** 中选择节点 **B**，因为它具有最低的 **dist[]** 值 **5**，并将其放入 **S**。B 的相邻节点是 **C**、**D** 和 **E**。我们根据算法更新对应于 **C**、**D** 和 E 的 dist[] 值。因此，数据结构的值变为：

dist[7]={0,5,6,12,13,∞,∞}
Q={C,D,E,F,G}
S={A,B}

此轮后的距离和最短路径为：

**第三轮** - 我们从 **Q** 中选择节点 **C**，因为它具有最低的 dist[] 值 6，并将其放入 S。C 的相邻节点是 D 和 F。我们更新对应于 D 和 F 的 dist[] 值。因此，数据结构的值变为：

dist[7]={0,5,6,8,13,10,∞}
Q={D,E,F,G}
S={A,B,C}

此轮后的距离和最短路径为：

**第四轮** - 我们从 **Q** 中选择节点 **D**，因为它具有最低的 **dist[]** 值 8，并将其放入 S。D 的相邻节点是 E、F 和 G。我们更新对应于 **E**、**F** 和 **G** 的 **dist[]** 值。因此，数据结构的值变为：

dist[7]={0,5,6,8,10,10,18}
Q={E,F,G}
S={A,B,C,D}

此轮后的距离和最短路径为：

**第五轮** - 我们可以从 **Q** 中选择节点 E 或节点 **F**，因为它们都具有最低的 **dist[]** 值 **10**。我们选择其中一个，例如 **E**，并将其放入 **S**。**D** 的相邻节点是 **G**。我们更新对应于 G 的 **dist[]** 值。因此，数据结构的值变为：