计算机网络中的最短路径算法

在从发送方向接收方传输数据包的过程中，数据会经过许多路由器和子网。因此，为了提高数据包的传输效率并减少网络流量，我们必须找到最短的路径。在本文中，我们将讨论用于寻找最短路径的算法。

什么是最短路径路由？

它指的是那些用于确定数据包在网络中从发送方到接收方之间的最短路径的算法。最短距离最小成本，以及最短时间。

• 它主要用于构建一种图或子网结构，其中路由器被作为节点来使用，而连接这些节点的线路则被看作是一种通信路径。
• “跳跃次数”是用于衡量距离的一个参数。
• 跳跃次数这是一个表示数量的数字。路由器如果跳数达到6，那就意味着有6个路由器/节点，以及连接它们的6条边。
• 另一个衡量指标就是地理距离，比如以公里为单位来表示。
• 我们可以将弧线上的标签视为带宽、平均流量、距离、通信成本、测量到的延迟、平均排队长度等参数的函数。

常见的短路径算法

• 迪杰斯特拉算法
• 贝尔曼-福特算法
• 弗洛伊德-沃舍尔算法

迪杰斯特拉算法

那个迪杰斯特拉算法这是一种贪婪算法，用于找出给定图中某个节点与所有其他节点之间的最小距离。在这里，我们可以将节点视为路由器，而将整个图视为一个网络。该算法利用边的权重以及节点之间的距离来寻找最短的路由路径。

算法：

• 初始化：
  将源点的距离设置为0，其余所有点的距离则设置为无穷大。
  将所有未访问的节点标记为已访问。
  将每个节点的 predecessor 设置为 null。
• 选择当前节点：
  在所有未被访问的节点中，选择当前距离最小的那个节点。
• 更新邻居信息：
  对于当前节点所连接的、尚未被访问的每一个邻居节点N来说：

• 计算：
  newDist = current节点的距离 + weight(current, N)
• If newDist < distance[N]那么：
  • 更新/补充信息距离[N] = newDist
  • 更新信息/数据前任[N] = 当前

• 马克的访问记录：
  将当前节点标记为已访问的节点（之后不会再检查该节点了）。
• 重复：
  如果仍然存在未被访问的节点，请返回到步骤2。
• 结束：
  现在，距离信息中包含了最短路径的成本信息；可以利用这些 predecessor 信息来重建出具体的路径。

示例：

考虑图G：

现在，我们将从节点0开始，逐一对图1进行标准化处理。

与0最近的邻居是2和1，因此我们先对它们进行标准化处理。

同样地，对于其他节点来说，我们也会进行归一化处理，确保它们不会形成循环。同时，我们还会记录那些已经被访问过的节点。

贝尔曼-福特算法

那个贝尔·曼·福德的该算法是一种单源图搜索算法，它能够帮助我们找到给定图中从起点顶点到其他任意顶点之间的最短路径。我们可以在无权重和有权重的图中都使用这种算法。不过，这种算法的执行速度比较慢。迪杰斯特拉算法此外，它还可以使用负的边权重。

算法

首先，我们将距离数组dist中的所有顶点v的初始值设为INFINITY。

2. 然后，我们随机选择一个顶点作为顶点0，并将dist[0]的值设为0。

3. 然后，通过多次比较每个节点到源节点的距离之和与边的权重，来迭代更新每个节点到源节点的最小距离（dist[v]）。具体操作需要重复 N-1 次。

4：为了识别存在负边循环的情况，需要借助以下方法，再进行一次边的松弛操作。

• 我们可以说，当任意一条边uv满足以下条件时，就存在负循环：即从源节点到该边的距离dist[u]与该边的权重weight之和小于到最大节点的当前距离dist[v]。
• 这意味着，如果没有任何一条边满足case1的条件，那么就可以确定不存在负环。

例如：Bellman-Ford算法能够检测图中的负环。

考虑一下图G：

步骤1：

步骤2：

步骤3：

步骤4：

步骤5：

结果：该图中，从节点D到节点F，然后再到节点E的路径中存在一个负循环。

弗洛伊德-沃舍尔算法

那个弗洛伊德-沃舍尔算法该算法用于找到给定图中任意两个节点之间的最短路径。它会维护一个表示各顶点对之间距离的矩阵。该算法会不断迭代这个矩阵，直到找到最短路径为止。

算法：

1: 利用关于该图表的数据，构建一个矩阵。

2: 通过将所有顶点都视为中间节点，我们需要更新最终的矩阵。

需要注意的是，这一过程意味着我们每次选择一个顶点后，都会更新包含该顶点的最短路径。此时，该顶点就成为了这条路径上的一个中间点。

4：当我们选择某个顶点，比如编号为k的顶点时，根据之前的计算，我们已经知道所有编号为P{0,1,2…,k-1}的顶点都可能是该路径的中间点。

5: 在处理源顶点和目的顶点 I,j 时，我们必须考虑以下子点。

• 如果顶点k不属于从I到j的最短路径的一部分，那么我们就不需要修改dist[i][j]的值。也就是说，该值将保持不变。
• 如果顶点 k 确实属于从 I 到 j 的最短路径的一部分，那么需要将 dist[i][j] 更新为 dist[i][k] 与 dist[k][j] 的总和。不过需要注意的是，只有当 dist[i][j] 大于这个数值时，才需要更新 dist[i][j]。

以给定的图G为例，

步骤1：

步骤2：

步骤3：

步骤4：

步骤5：

步骤6：

步骤7：