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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,实验二,路由协议,Dijkstra,算法的编程与实现,一、实验目的,介绍,Dijkstra,算法,Dijkstra,算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。已知条件是整个网络拓扑和各链路的长度,。,讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。,二、实验原理,令,D,(,v,),为源结点,(,记为结点,1),到某个结点,v,的距离，它就是从结点,1,沿某一路径到结点,v,的所有链路的长度之和。再令,l(,i,j,),为结点,i,至结点,j,之间的距离。整个算法只有以下两个部分：,(1),初始化,令,N,表示网络结点的集合。先令,N,=1,。对所有不在,N,中的结点,v,，写出,在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替。对于上述例子，可以使,D,(,v,)=99,。,(2),寻找一个不在,N,中的结点,w,，其,D,(,w,),值为最小。把,w,加入到,N,中。然后对所有不在,N,中的结点,v,，用,D,(,v,),D,(,w,)+,l,(,w,v,),中的较小的值去更新原有的,D,(,v,),值，即：,D,(,v,)Min,D,(,v,),D,(,w,)+,l,(,w,v,),(3),重复步骤,(2),，直到所有的网络结点都在,N,中为止。,例如：,步骤,N,D,(2),D,(3),D,(4),D,(5),D,(6),初始化,1,2,5,1,1,1,4,2,4,2,2,1,4,5,2,3,1,4,3,1,2,4,5,3,1,2,4,4,1,2,3,4,5,2,1,2,4,5,1,2,3,4,5,6,2,3,1,2,现在我们对以上的最短路径树的找出过程进行一些解释。,因为选择了结点,1,为源结点，因此一开始在集合,N,中只有结点,1,。结点,1,只和结点,2,3,和,4,直接相连，因此在初始化时，在,D,(2),，,D,(3),和,D,(4),下面就填入结点,1,到这些结点相应的距离，而在,D,(5),和,D,(6),下面填入。,下面执行步骤,1,。在结点,1,以外的结点中，找出一个距结点,1,最近的结点,w,，这应当是,w,=4,，因为在,D,(2),，,D,(3),和,D,(4),中，,D,(4)=1,，它的之值最小。于是将结点,4,加入到结点集合,N,中。这时，我们在步骤,1,这一行和,D,(4),这一列下面写入，数字,1,表示结点,4,到结点,1,的距离，数字,1,的圆圈表示结点,4,在这个步骤加入到结点集合,N,中了。,接着就要对所有不在集合,N,中的结点（即结点,2,3,5,和,6,）逐个执行（,E-1,）式。,对于结点,2,，原来的,D,(2)=2,。现在,D,(,w,)+,l,(,w,v,)=,D,(4)+,l,(4,2)=1+2=3,D,(2),。因此结点,2,到结点,1,距离不变，仍为,2,。,对于结点,3,，原来的,D,(3)=5,。现在,D,(,w,)+,l,(,w,v,)=,D,(4)+,l,(4,3)=1+3=4,D,(3),。因此结点,3,到结点,1,的距离要更新，从,5,减小到,4,。,对于结点,5,，原来的,D,(5)=,。现在,D,(,w,)+,l,(,w,v,)=,D,(4)+,l,(4,5)=1+1=2,D,(5),。因此结点,5,到结点,1,的距离要更新，从减小到,2,。,对于结点,6,，现在到结点,1,的距离仍为。,步骤,1,的计算到此就结束了,下面执行步骤,2,。在结点,1,和,4,以外的结点中，找出一个距结点,1,最近的结点,w,。现在有两个结点（结点,2,和,5,）到结点,1,的距离一样，都是,2,。我们选择结点,5,（当然也可以选择结点,2,，最后得出的结果还是一样的）。以后的详细步骤这里就省略了，读者可以自行完成剩下的步骤。,三、算法实现,输入输出格式,输入格式,:,第,1,行,:,一个数,n,，代表有,n,个节点,第,2-n+1,行,:,每行,n,个数，代表图的邻接矩阵，没有边相连为,-1,输出格式,:,第,1,行,:n-1,个数，分别是,1,号节点到,2-n,号节点的最短路径，代码见如下：,思考题,对于例题中的每个结点写出以该结点为根结点的最小生成树。,谢谢！,