《计算机网络教学资料》实验二

1、实验二路由协议D i j kst r a算法的编程 j 与实现一、实验目的介绍Di jkstra算法Dijkstra算法是典型最短路算法，用于计算一个节点 到其他所有节点的最短路径。主要特点是以起始点为中心 向外层层扩展，直到扩展到终点为止。已知条件是整个网 络拓扑和各链路的长度。讨论这种算法，即寻找从源结点 到网络中其他各结点的最短路径。二、实验原理r令(0为源结点(记为结点1)到某个结点啲距离，它 就是从结点1沿某一路径到结点啲所有链路的长度之和。 再令1(厶丿)为结点了至结点丿之间的距离。整个算法只有 以下两个部分：(1) 初始化令憔示网络结点的集合。先令二lo对所有不在幷 中的结点耳写

2、出f/(l,v)若结点V与结点1直接相连(V)= OO若结点V与结点1不直接相连在用计算机进行求解时，可以用一个比任何路径长 度大得多的数值代替对于上述例子，可以使W)= 99o(2) 寻找一个不在肿的结点昭 其(分值为最小。把劝口入 到肿。然后对所有不在种的结点卩，用D3 + 7U 7)的技小的値去更薪原肴的(卩)值，即：Z?(r) *-MinZ?(r), Dw)+ /(%v)(3) 重复步骤(2),直到所有的网络结点都在肿为止。例如:步骤N0(2)D。(4)0(5)0(6)初始 化125100OO11,4242OO21,4,5231431,2, 4, 53124411,2,3,4,5212

3、451，2, 3, 4, 5, 62312现在我们对以上的最短路径树的找出过程进行一些解释。因为选择了结点1为源结点，因此一开始在集合神只 有结点1。结点1只和结点2, 3和4直接相连，因此在初始 化时，在2?(2), (3)和(4)下面就填入结点1到这些结点 相应的距离，而在(5)和(6)下面填入a。勰黑勸跖鑫欷鑼礬歌器数字I的下面执行步骤1。在结点1以外的结点中，找出一个距 结点1最近的结点昭这血当是二4,囱为在， 和中，Z?(4) = 1,它的之值最小。于是将结点4加入 刼结点秦合神。这此 我彳门在步骤1这一行和(4)这一刻和接馨溫會您合神的结点(即结点235对于结点2,原来的(2) =

4、 2o现在(分+ 1(叽v)= 織處蘇严0(2)。因此结点2到结点对于结点3,原来的(3)二5o现在(內+ g v) =(4) + 7(4, 3)二 1 + 3 二 4 (3)。因此结点3到结 点1的距离要更新，从5减小到4。对于结点5,原来的力(5)二o现在0(讷+ 7( v) =(4) + 7(4, 5)二 1 + 1 = 2 (5)。因此结点5到结 点1的距离要更新，从8减小到2。对于结点6,现在到结点1的距离仍为8。步骤1的计算到此就结束了下面执行步骤2。在结点1和4以外的结点中，找出一 个距结点1最近的结点现在有两个结点(结点2和5)到 结点1的距离一样，都是2。我们选择结点5 (当然也可以 选择结点2,最后得出的结果还是一样的)。以后的详细 步骤这里就省略了，读者可以自行完成剩下的步骤。三、算法实现r输入输岀格式输入格式：第1行:一个数n,代表有n个节点第2-n+1行:每行n个数，代表图的邻接矩阵，没有边相连另T输出格