[简答题]设网络拓扑如题44图所示。请利用Dijkstra最短路径算法计算节点x到网络中所有节点的最短路径,填写题44表中序号处的内容。

注:如果某个节点在选择下一跳节点时,有多个节点的最短路径相同,则选择节点编号小的节点作为下一跳节点。例如,如果节点x到节点y和节点z的路径代价相同,而且都是x到所有下一跳节点中的最短路径,则选择y为x的下一跳节点。

正确答案:

(1)W
(2)6
(3)W
(4)5
(5)W
(6)3
(7)W
(8)2
(9)W

(10)3
(11)W
(12)7

题目解析

链路状态路由选择算法就是利用Dijkstra 算法求最短路径:
• D(v):到本次迭代为止,源结点(计算结点)到目的结点v的当前路径距离。初始化时,如果结点v和源结点直接相连,那么D(v)就是其链路上的权值,否则就是∞。
• P(v):到本次迭代为止,在源结点到目的结点v的当前路径上,结点v的前序结点。
• C(x, y):结点x与结点y之间直接链路的费用,如果x和y之间没有之间链路相连, 则 c(x, y)= ∞。
• S:结点的集合,用于存储从源结点到该结点的最短路径已求出的结点集合,初始值只有源点本身。 

故各节点x到网络中所有节点的最短路径:


故得到x上的转发表:


扫描二维码
免费搜题、免费刷题、免费查看解析