计算机网络中的最短路径算法
在计算机网络中，最短路径算法旨在找到网络节点之间的最佳路径，从而使路由成本最小化。它们是图论中提出的最短路径算法的直接应用。
解释
考虑一个网络由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到其他每个节点的最短路径。
FloydWarshall算法
输入-成本邻接矩阵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的最短成本。