algorithm - 链路状态路由协议 - Dijkstras 算法

Question

N- 网络 R- 路由器

在上图中，你可以看到一个关于链路状态路由协议的问题。当您为此执行R3 的 Dijkstra 算法时，我知道您从添加 N3 和 N4 开始，然后查看成本，2 小于 4，因此 N4 变为永久，但当 N4 变为永久时，是否添加 R4 和 R7 或执行你只选择其中之一？

Answer 1

Dijkstra 算法的关键在于，在处理节点之前，您永远不会丢弃它。

Step 1 : R3
N4 - 2
N3 - 4

Step 2 : N4
R7 - 3
N3 - 4
R4 - 6

Step 3 : R7
N3 - 4
R4 - 6
N6 - 9

在此步骤中，您将 N3 作为与剩下的 R3 最接近的，因此您执行 N3

Step 4 : N3
R4 - 6
R8 - 6
R2 - 6
N6 - 9

请注意，在每一步之后都有一个排序。因此，最低优先级队列应该会有所帮助。

Answer 2

这个例子有点令人困惑，因为箭头，但我想我们可以假设这是一个带有顶点集的无向图N union R。

来自wikipedia，这些是 Dijkstra 的步骤：

1. 为每个节点分配一个暂定的距离值：对于我们的初始节点将其设置为零，对于所有其他节点将其设置为无穷大。
2. 标记所有未访问的节点。将初始节点设置为当前节点。创建一组未访问节点，称为未访问集，由除初始节点之外的所有节点组成。
3. 对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。
4. 当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问并将其从未访问集中删除。被访问的节点将永远不会被再次检查。
5. 如果目标节点已被标记为已访问（当规划两个特定节点之间的路线时），或者如果未访问集中节点之间的最小暂定距离为无穷大（当规划完整遍历时），则停止。算法完成。
6. 选择标记为最小暂定距离的未访问节点，并将其设置为新的“当前节点”，然后返回步骤 3。

让我们根据您的情况来看看这些步骤。

• 广告1。R3是初始节点，所以它得到 distance 0。
• 广告2。R3是当前的。
• 广告3。访问N3和N4并将它们的暂定距离分别设置为4和。2
• 广告4。标记R3为完成。
• 广告 5。--
• 广告 6。选择N4为当前节点并返回步骤 3。
• 广告3。访问R4和R7并将它们的暂定距离分别设置为6和。3
• 广告4。标记N4为完成。
• 广告 5。--
• 广告 6。选择R7为当前节点并返回步骤 3。

等等。