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

Question

N-网络 R-路由器

在上面的图片中，可以看到一个关于链路状态路由协议的问题。为此，我知道你首先加入N3和N4，然后看成本，2小于4，所以N4变成永久的，但是当N4变成永久的时候，它会加上R4和R7或者你只是选择其中一个？

Answer 1

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

从wikipedia，这些都是Dijkstra的步骤：

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

让我们来看看这些步骤你的情况。

• Ad1。 R3是初始节点，所以它得到距离0。
• Ad2。 R3是最新的。
• Ad3。请访问N3和N4，并分别将它们的试验距离设置为4和2。
• Ad4。完成后，标记R3。
• Ad5。 -
• Ad6。选择N4作为当前节点并返回步骤3.
• Ad3。请访问R4和R7，并分别将它们的临时距离设置为6和3。
• Ad4。完成后，标记为N4。
• Ad5。 -
• Ad6。选择R7作为当前节点并返回步骤3。

依此类推。

Answer 2

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 

注意，每一步之后有一个排序。所以最低优先级队列应该有所帮助。