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

更新于 2025/2/24 14:52:17

在计算机网络中，最短路径算法旨在找到网络节点之间的最佳路径，从而最小化路由成本。它们是图论中提出的最短路径算法的直接应用。

解释

假设一个网络由 N 个顶点(节点或网络设备)组成，这些顶点通过 M 条边(传输线)连接。每条边都与一个权重相关联，表示传输线的物理距离或传输延迟。最短路径算法的目标是沿着边找到任意一对顶点之间的路由，因此边的权重总和最小。如果边的权重相等，最短路径算法旨在找到具有最少跳数的路由。

一些常见的最短路径算法是 -

以下部分介绍了这些算法中的每一个。

输入 - 表示网络的图;以及源节点 s

输出 - 从 s 到所有其他节点的最短路径。

将从 s 到所有节点的距离初始化为无穷大 (∞);到自身的距离初始化为 0;一个大小为 |V|(节点数)的数组 dist[]，除 dist[s] 外，所有值均为 ∞。
迭代计算最短距离。对除 s 之外的每个节点重复 |V|- 1 次 −
- 对连接顶点 u 和 v 的每个边重复此操作 −
  - 如果 dist[v] > (dist[u] + 边 u-v 的权重)，然后
    - 更新 dist[v] = dist[u] + 边 u-v 的权重
数组 dist[] 包含从 s 到每个其他节点的最短路径。

输入 - 表示网络的图;以及源节点 s

输出 - 以 s 为根节点的最短路径树 spt[]。

一个距离数组 dist[]，大小为 |V|(节点数)，其中 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 到每个其他节点的最短路径。

输入 - 成本邻接矩阵 adj[][]，表示网络中节点之间的路径。

输出 - 最短路径成本矩阵 cost[][]，显示图中每对节点之间的成本最短路径。

按如下方式填充 cost[][]:
- 如果 adj[][] 为空，则 cost[][] = ∞(无穷大)
- 否则 cost[][] = adj[][]
N = |V|，其中 V 表示网络中的节点集。
重复 k = 1 到 N −
- 重复 i = 1 到 N −
  - 重复 j = 1 到 N −
    - 如果 cost[i][k] + cost[k][j] < cost[i][j]，则
      - 更新 cost[i][j] := cost[i][k] + cost[k][j]
矩阵 cost[][] 包含从每个节点 i 到每个其他节点 j 的最短成本。