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

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

解释

假设一个网络由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[]。

一个大小为|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 到每个其他节点的最短路径。

输入 − 一个代表网络中节点之间路径的成本邻接矩阵 adj[][] 。

输出 − 一个代表图中每对节点之间以成本为单位的最短路径的最短路径成本矩阵 cost[][] 。

填充 cost[][] 如下：
- 如果 adj[][] 为空，则 cost[][] =∞（无穷大）
- 否则 cost[][] = adj[][]
N = |V| ，其中 V 表示网络中的节点集。
重复对于 k = 1 to N −
- 重复对于 i = 1 to N −
  - 重复对于 j = 1 to N −
  - 如果 cost[i][k] + cost[k][j] < cost[i][j] ，那么
  - 更新 cost[i][j] := cost[i][k] + cost[k][j]
矩阵 cost[][] 包含了每个节点 i 到其他每个节点 j 的最短路径成本。