计算机网络中的最短路径算法
在计算机网络中，路径" title="最短路径">最短路径算法" title="最短路径算法">最短路径算法旨在找到网络节点之间的最佳路径，从而使路由成本最小化。它们是图论中提出的最短路径算法的直接应用。
解释
考虑一个网络由N个顶点（节点或网络设备）组成，这些顶点由M条边（传输线）连接。每个边缘与权重相关联，该权重表示传输线的物理距离或传输延迟。最短路径算法的目标是在沿边缘的任意一对顶点之间找到一条路径，因此边缘的权重之和最小。如果边缘的权重相等，则最短路径算法旨在查找跳数最少的路由。
常见最短路径算法
一些常见的最短路径算法是-
贝尔曼·福特算法
Dijkstra的算法
弗洛伊德·沃舍尔算法
以下各节介绍了每种算法。
贝尔曼福特算法
输入-代表网络的图形；和一个源节点s
输出-从s到所有其他节点的最短路径。
将s到所有节点的距离初始化为无限（∞）；与自身的距离为0；| V |大小的数组dist [] （节点数），除dist [s]之外所有值均为∞ 。
迭代计算最短距离。对每个节点重复| V |-1次，除了s-
如果dist [v] > （dist [u] +边缘uv的权重），则
更新dist [v] = dist [u] +边缘uv的权重
对连接顶点u和v的每个边重复-
数组dist []包含从s到其他每个节点的最短路径。
Dijkstra的算法
输入-代表网络的图形；和一个源节点s
输出-最短路径树spt []，以s为根节点。
初始化-
大小| V |的距离dist []的数组 （节点数），其中dist [s] = 0且dist [u] =∞（无限），其中u表示图中除s之外的节点。
数组Q，包含图中的所有节点。当算法运行完成时，Q将为空。
一个空集S，将向其添加访问的节点。当算法运行完成时，S将包含图中的所有节点。
当Q不为空时重复-
如果（dist [u] +边缘uv的权重） < dist [v]，则
更新dist [v] = dist [u] +边缘uv的权重
从Q中删除具有最小dist [u]且不在S中的节点u。在第一次运行中，将删除dist [s]。
将u添加到S，将u标记为已访问。
对于与u相邻的每个节点v，将dist [v]更新为-
数组dist []包含从s到其他每个节点的最短路径。
Floyd Warshall算法
输入-成本邻接矩阵adj [] []，表示网络中节点之间的路径。
输出-最短路径成本矩阵cost [] []，它显示了图中图中每对节点之间的最短路径。
填充cost [] []如下：
如果adj [] []为空，则cost [] [] =∞（无限）
其他费用[] [] =调整[] []
N = | V | ，其中V代表网络中的节点集。
对于重复K = 1至N -
对于重复J = 1至N -
更新成本[i] [j]：=成本[i] [k] +成本[k] [j]
如果cost [i] [k] + cost [k] [j] < cost [i] [j]，则
对i = 1到N −重复
矩阵cost [] []包含从每个节点i到每个其他节点j的最短成本。
以上是 计算机网络中的最短路径算法 的全部内容， 来源链接： utcz.com/z/361748.html
