5种语言实现 | 使用Dijkstra算法从起点到所有节点找到最短路径

5种语言实现 | 使用Dijkstra算法从起点到所有节点找到最短路径

Dijkstra算法是计算机科学中一个非常重要的算法，用于解决图论中的最短路径问题。本文将详细介绍Dijkstra算法的基本原理、实现步骤，并提供多种编程语言的代码实现。

给定一个带权重的图和图中的一个起点，找到该点到图中所有其他节点的最短路径。注意：给定的图中不包含任何负边。

使用邻接矩阵的Dijkstra算法

思路是以给定起点为根节点生成一个最短路径树（SPT）。维护一个包含两个集合的邻接矩阵，

• 一个集合包含在最短路径树中的节点，
• 另一个集合包含尚未包含在最短路径树中的节点。

算法的每个步骤中，找到一个在另一个集合中（尚未包含的集合）且距离起点最小的节点。

算法

1. 创建一个集合sptSet（最短路径树集合），用于跟踪包含在最短路径树中的节点，即已计算和完成的距离起点的最小距离。初始时，此集合为空。
2. 为输入图中的所有节点赋予一个距离值。将所有距离值初始化为无穷大。将起点的距离值设置为0，以便首先选择它。

当sptSet未包含所有节点时

• 选择一个不在sptSet中且具有最小距离值的节点u。
• 将u包含到sptSet中。
• 然后更新u的所有邻接节点的距离值。
• 为了更新距离值，迭代遍历所有邻接节点。
• 对于每个邻接节点v，如果u到v的距离值（从起点开始）加上边权重小于v的距离值，则更新v的距离值。

注意：我们使用一个布尔数组sptSet[]来表示包含在SPT中的节点集合。如果值sptSet[v]为true，则表示节点v包含在SPT中，否则不包含。数组dist[]用于存储所有节点的最短距离值。

Dijkstra算法的示例

为了理解Dijkstra算法，我们来看一个图，并找到从起点到所有节点的最短路径。考虑下面的图和起点src = 0。

步骤1：

• 集合sptSet最初为空，节点的距离值分别是{0, INF, INF, INF, INF, INF, INF, INF}，其中INF表示无穷大。
• 现在选择具有最小距离值的节点。选择节点0，并将其包含在sptSet中。因此，sptSet变为{0}。将0包含在sptSet中后，更新其相邻节点的距离值。
• 节点0的相邻节点是1和7。将1和7的距离值更新为4和8。
  以下子图显示了节点及其距离值，只显示具有有限距离值的节点。包含在最短路径树中的节点以绿色显示。

步骤2：

• 选择具有最小距离值且尚未包含在SPT中（不在sptSet中）的节点。选择节点1并将其添加到sptSet中。
• 因此，sptSet现在变为{0, 1}。更新节点1的相邻节点的距离值。
• 节点2的距离值变为12。

步骤3：

• 选择具有最小距离值且尚未包含在SPT中（不在sptSet中）的节点。选择节点7。因此，sptSet现在变为{0, 1, 7}。
• 更新节点7的相邻节点的距离值。节点6和8的距离值变为有限值（分别为15和9）。

步骤4：

• 选择具有最小距离值且尚未包含在SPT中（不在sptSet中）的节点。选择节点6。因此，sptSet现在变为{0, 1, 7, 6}。
• 更新节点6的相邻节点的距离值。节点5和8的距离值被更新。

我们重复上述步骤，直到sptSet包含了给定图的所有节点。最后，我们得到以下最短路径树（SPT）。

代码实现

以下是Dijkstra算法在不同编程语言中的实现：

• C++语言：
• Java语言：
• Python 3 语言：
• C#语言：
• Javascript：

输出

时间复杂度：O(V^2)
辅助空间：O(V)

注意

• 该代码计算了最短距离，但没有计算路径信息。可以创建一个父节点数组，在更新距离时更新父节点数组，并使用它来显示从源到不同节点的最短路径。
• 该实现的时间复杂度是O(V^2)。如果使用邻接表表示输入图，可以借助二叉堆将其减少为O(E * log V)。更多详情，请参阅邻接表表示的Dijkstra算法。
• Dijkstra算法对具有负权重环的图不起作用。

Dijkstra算法的应用

• 谷歌地图使用Dijkstra算法显示起点和目标点之间的最短距离。
• 在计算机网络中，Dijkstra算法是各种路由协议的基础，例如OSPF（开放最短路径优先）和IS-IS（中间系统到中间系统）。
• 交通和交通管理系统使用Dijkstra算法来优化交通流量，减少拥堵，并计划车辆的最高效路径。
• 航空公司使用Dijkstra算法来规划最小化燃料消耗、减少旅行时间的飞行路径。
• Dijkstra算法在电子设计自动化中用于在集成电路和大规模集成（VLSI）芯片上进行路由连接。