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

最短路径路由

在此算法中，为了选择路由，算法会发现两个节点之间的最短路径。它可以使用多跳、以公里为单位的地理区域或弧线标记来测量路径长度。

弧线标记

弧线标记可以使用平均排队、每小时标准测试数据包的传输延迟来完成，或者根据带宽、平均距离流量、通信成本、平均队列长度、测量延迟或其他一些因素来计算。

图中的最短路径路由

在最短路径路由中，拓扑通信网络使用有向加权图来定义。图中的节点定义交换组件，图中的有向弧定义交换组件之间的通信连接。每个弧都有一个权重，它定义了在特定方向上两个节点之间共享数据包的成本。

此成本通常为正值，可以表示延迟、吞吐量、错误率、财务成本等因素。两个节点之间的路径可以经过各种中间节点和弧。最短路径路由的目标是找到两个节点之间总成本最低的路径，其中路径的总成本是该路径中弧成本的总和。

例如，Dijikstra 使用节点标记其与更知名路线上的源节点的距离。最初，所有节点都标记为无穷大，随着算法的进行，标签可能会发生变化。图中显示了标记图。

可以按照以下方式通过各种传递完成，以 A 为源。

• 传递 1. B (2, A), C(∞,−), F(∞,−), e(∞,−), d(∞,−), G 60

• 传递 2. B (2, A), C(4, B), D(5, B), E(4, B), F(∞,−), G(∞,−)

• 传递 3. B(2, A), C(4, B), D(5, B), E(4, B), F(7, C), G(9, D)

我们可以看到，A 和 G 之间有两条路径。一条通过 ABCFG，另一条通过 ABDG。第一条路径长度为 11，而第二条路径长度为 9。因此，选择第二条路径，即 G (9, D)。类似地，节点 D 也有三条从 A 出发的路径，即 ABD、ABCD 和 ABED。第一条路径长度为 5，其余两条路径长度为 6。因此，选择第一条路径。

在各种遍历中搜索所有节点，最后，将路径长度最短的路线设为永久路线，并将该路径的节点用作下一轮的工作节点。