《北邮通信网实验二报告》由会员分享，可在线阅读，更多相关《北邮通信网实验二报告（17页珍藏版）》请在金锄头文库上搜索。
1、通信网理论基础实验报告实验二：端间最短路径算法的仿真实现 27班项明钧2013210731 27班唐睿2013210742一、实验目的通信网络中为传输信息，需要求解网络中端点之间的最短距离和路由。此时网络可以用图来表示，每条边的权可为该边的距离、成本或容量等物理意义。端间最短径问题主要分为两种情况：寻找指定端至任意其它端之间的最短距离和路由，可以使用Dijkstra算法解决；寻找任意两端之间的最短距离和路由, 使用Floyd算法解决。Dijkstra算法为标号置定法，通过依次置定指定端与当前端的最短距离和回溯路由来实现；Floyd算法为标号修正法，通过初始化图的距离矩阵和路由矩阵、并在迭代过程
2、中不断刷新最短距离和路由信息，直至算法结束才能求出任意两点间的最短距离矩阵和前向（或反向）路由矩阵。本次实验要求利用MATLAB分别实现Dijkstra算法和Floyd算法，针对输入的邻接距离矩阵，计算图中任意两点间的最短距离矩阵和路由矩阵，且能查询任意两点间的最短距离和路由。二、实验原理2.1 Dijkstra算法描述如下：D算法的每个端点的标号为，其中表示到的距离，而为端点是到最短路径的最后一个端点。图的每一边上有一个权。D0：初始，记，设的标号为。D1：对任一边，计算的值。在中选一边，设为。使，并令，并且的标号为。D2：当出现下面情况之一时停止。1）；2）但2.2 Floyd算法可描述如
3、下：给定图及其边的权F0：初始化距离矩阵和路由矩阵。其中：F1：对于已求得的和，依据下面的迭代求解和。F2：若，重复F1；若，终止。三、实验内容采用的语言：MATLAB数据结构：基本矩阵计算，基本数组计算主要函数：Dijkstra算法：1、初始化path矩阵path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=100 path(i,j)=i; end endend2、 各点最短距离矩阵生成for i=1:num x=al(i); for j=1:n newdistance(i,j)=distance(x)+a(x,j); end end 3、 比较所有点得
4、出一个最短距离并生成距离矩阵D for i=1:n if (newdistance(1,i)y) y=newdistance(1,i); u(1,1)=i; endEnd D(s,u(1,1)=y;4、 生成回溯路由矩阵path for i=2:num if (newdistance(i,u(1,1)=newdistance(1,u(1,1) r(1,1)=al(i); end end if (r(1,1)=0) r(1,1)=al(1); endpath(s,u(1,1)=r(1,1);5、 生成两点之间的具体路由数组luyou=zeros(1,n);luyou(n)=o;h=D(l,o);
5、for m=2:n if (path(l,o)=l) luyou(n-m+1)=path(l,o); o=path(l,o); else luyou(n-m+1)=l; endendFloyd算法：1、初始化path矩阵path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=100 path(i,j)=i; end endend2、 同时生成距离矩阵和路由矩阵for k=1:n for i=1:n for j=1:n if (D(i,k)+D(k,j)D(i,j)&(i=j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k)
6、 end end endEnd3、 生成两点之间的具体路由数组luyou=zeros(1,n);luyou(1)=s;h=D(s,t);for m=2:n if (path(s,t)=t) luyou(m)=path(s,t); s=path(s,t); else luyou(m)=t; endEnd4、 输出函数disp(D);disp(path);disp(h); disp(luyou);算法流程图：是将新顶点加入al中比较得出最短距离，同时赋值给距离矩阵和路由矩阵否计算al数组中各点到剩下顶点的距离所有顶点都已在al数组里？将顶点加入al数组中开始结束DijkstraFloyd：开始否否
7、否是是是修改路由矩阵Wij=Wik+WkjWijn?四、 实验数据与结论分析Dijkstra图一：邻接矩阵最短路径距离矩阵：回溯路由矩阵：端点对V4和V6距离和路由端点对V3和V4距离和路由图二：邻接矩阵最短路径距离矩阵回溯路由矩阵端点对V1和V7V3和V5V1和V6自定义图：邻接矩阵最短路径距离矩阵回溯路由矩阵端点对1和62和71和3Floyd：图一：邻接矩阵最短路径距离矩阵正向路由矩阵端点对V4和V6V3和V4 图二： 邻接矩阵：最短路径距离矩阵正向路由矩阵端点对V1和V7V3和V5V1和V6自定义图：邻接矩阵最短路径距离矩阵正向路由矩阵端点对1和62和71和3结论：Dijkstra由上述
8、三个图的例子可以看出，dijkstra算法是通过规定初始点儿求局部最优解从而解出到各点距离最短的贪婪算法，当给定起点s和终点t时，最短路径距离矩阵的第s行第t列数据即为最短路径，在回溯路由矩阵可以通过多次确定前一个经过点而确定最终的最短路径路由。Floyd由三个图的例子可以看出，Floyd算法是通过迭代运算消除不满足定理Wij=Wik+Wkj的情况，讲邻接矩阵的每行每列都遍历一次从而用距离更小的路径代替距离大的路径，最终达到生成任意两点之间最短距离和路由的矩阵。当给定起点s和终点t时，最短路径距离矩阵的第s行第t列数据即为最短路径，在正向路由矩阵中可以通过多次确定下一个需要经过的点而确定最短路
9、由。上述两种算法中，Floyd算了不需要边的权为非负这一条件，而Dijkstra需要。五、 实验问题和难点1、 图的等价表示方法，通过矩阵的行和列表示起点和终点，对应的值表示距离，（k,k)=0表示到自己的点距离为0，没有通路的两端点对应的矩阵里的值为100。2、 两点间的最短路径查询算法，Dijkstra通过遍历局部得出最优解，而Floyd通过迭代算法用新发现的最短距离层层替代原来的距离。3、 在进行Dijkstra遍历比较大小时，如何得出已有各点到未知点的距离以及比较各距离的大小成为一难点。据此我组建了num*n的newdistance矩阵，保存以确定的num个顶点到其余顶点的最短距离，将
10、已有顶点的距离设为1000，并且通过逐次比较行与列的大小求出其中最短的距离。4、 由于Dijkstra算法的复杂性，求回溯顶点时如何从newdistance矩阵中推出回溯顶点的值比较难。为此我将第一行设为最小值，通过逐行比较得出最小距离，然后通过将得出的最小距离重新逐行比较得出对应的顶点值。5、 采用Dijkstra算法时最短距离矩阵正确，而最短路由矩阵其他位置都对，只有第四行第六列的值不对，为此我思考了好久。最后在路由矩阵各行是互不影响生成的基础上发现了第35行代码将a(x,j)错写成D(x,j),经过修改后程序运行成功。六、扩展的实验内容（选作部分）（1）比较D算法和F算法在功能和算法复杂
11、度上的性能功能： Dijkstra不能计算有负权边的，Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra属于贪心算法，是两重循环。Floyd是解决任意两点间的最短路径的一种算法，可以计算有负权边的的，并可检测负权回路。可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd属于动态规划，是三重循环。 算法复杂度： Dijkstra算法的时间复杂度为O(n2)，空间复杂度取决于存储方式，邻接矩阵为O(n2)，由于只需要计算源点到任意点的距离和路径，所以 Di
12、jkstra算法复杂度更低一些。但是如果需要计算距离矩阵的话，他的时间复杂度也为O(n3)。Floyd时间复杂度为O(n3)，即顶点数的三次方，空间复杂度为O(n2)。Floyd的应用范围比迪杰斯特拉更广。（2） 探讨可降低算法复杂度的算法：Dijkstra：在我的MATLAB程序中，dijkstra的距离矩阵和路由矩阵的每一行都是各自独立生成的，互不影响，因此也导致了一些重复计算。经过思考，我发现在某一行新算出的那个回溯点如果包含在已经算出的那一行中时，那么从原点到该回溯点的距离和矩阵便可以直接从指间算出的那一行中寻找，从而大大减少了计算次数Floyd：优化的具体思路为，构造迭代矩阵D(k)=(d(k)ij)，计算两点Vi和Vj之间最短路时对待插入的节点Vr先进行路长比较，如果d(k-1)ird(k-1)ij或d(k-1)rjd(k-1)ij,则说明插入点Vr后，点Vii经过节点Vr到达点Vj的路长不会比原来的短，于是不用再计d(k-1)ir+d(k-1)rj，进入下一个节点的搜索。经过优化后时间复杂度变为O(n3/2),约为原来的一半。七、实验心得 此次是第
