algorithm - 链路状态路由协议(protocol)——Dijkstras算法

Question

N-网络 R-路由器

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

Answer 1

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

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

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

让我们针对您的情况看看这些步骤。

• 广告 1。 R3 是初始节点，因此它的距离为 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步。

等等。