DCN 最短路径算法

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

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

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

• Bellman Ford 算法

• Dijkstra 算法

• Floyd Warshall 算法

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

输入 - 表示网络的图;以及源节点 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 的最短成本。