N-网络 R-路由器
在上面的图片中,可以看到一个关于链路状态路由协议的问题。为此,我知道你首先加入N3和N4,然后看成本,2小于4,所以N4变成永久的,但是当N4变成永久的时候,它会加上R4和R7或者你只是选择其中一个?
N-网络 R-路由器
在上面的图片中,可以看到一个关于链路状态路由协议的问题。为此,我知道你首先加入N3和N4,然后看成本,2小于4,所以N4变成永久的,但是当N4变成永久的时候,它会加上R4和R7或者你只是选择其中一个?
这个例子有点混乱,因为有箭头,但我想我们可以假设这是一个无向图,顶点集为N union R
。
从wikipedia,这些都是Dijkstra的步骤:
让我们来看看这些步骤你的情况。
R3
是初始节点,所以它得到距离0
。R3
是最新的。N3
和N4
,并分别将它们的试验距离设置为4
和2
。R3
。N4
作为当前节点并返回步骤3.R4
和R7
,并分别将它们的临时距离设置为6
和3
。N4
。R7
作为当前节点并返回步骤3。依此类推。
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
注意,每一步之后有一个排序。所以最低优先级队列应该有所帮助。
N4和N3都没有传出边缘,那么这些路径是否是无向的?另外,我想你是从R3开始的,你打算到哪里? – anoopelias 2013-04-29 11:00:11