网络原理实验报告(Dijkstra).docx

网络原理实验报告编程实现Dijkstra路由算法姓名： 班级：学号：教师： 1. 实验目的运用各种编程语言实现基于Dijkstra算法的路由软件。PS：这里使用的是JAVA语言2. 实验意义通过本实验，使学生能够对路由原理和路由算法有进一步的理解和掌握。3. 实验背景DIJKSTRA算法描述如下：设：c(i,j): 结点i至结点j之间链路的代价，若i,j不直接相连，则为无穷大。D(v): 当前从源结点至目的结点V之间路由的代价。p(v): 从源结点至目的结点V之间路由中V之前的结点N: 已经知道最优路径的结点集合1 Initialization:2 N = A3 for all nodes v4 if v adjacent to A5 then D(v) = c(A,v)6 else D(v) = infty7 Loop 8 find w not in N such that D(w) is a minimum9 add w to N10 update D(v) for all v adjacent to w and not in N:11 D(v) = min( D(v), D(w) + c(w,v) )12 /* new cost to v is either old cost to v or known13 shortest path cost to w plus cost from w to v */14 until all nodes in N4. 实验步骤（1） 选择合适的编程语言编程实现基于Dijkstra算法的路由软件。（2） 输入不同的网络拓扑和链路代价测试和验证自己的路由软件。5. 实验环境（1） 实验语言：JAVA（2） 实验平台：Eclipse（3） 引用库函数：随机（Random）库6. 算法思想理解与描述在编写代码时，我曾遇到过两个问题也是最容易碰到的难题，这里我介绍一下自己的解决方法：A Dijkstra算法究竟是怎样计算最短距离和最短路径的？也许如果只是要我们写一个算法，求最短路径和最小距离，那么我们可能不同的人有不同的“自然而然”的思路，而且肯定很多并不与Dijkstra算法雷同，但令我们头疼的是：这里是别人写好了一个算法，我们得去理解，而不是让我们自己去操刀。在我看来，与其看那些枯燥无味的算法文字叙述还不如看图看表我就是看了（中文版）P240的表4-3（它对应着P238的图4-27）才明白是“怎么算的”，这里我就说下自己的理解，也不过就是几句话而已：1. 一开始，将源节点到各点的直达距离作为最短距离；PS：这里还是要理解表中D()和p()的含义D()就是刚才说的到目标节点的“目前认为”的最短距离，而p()是“当前认为”的最短路径上到目标节点的前一节点（至少我是这么认为的：如果只求最短距离，p()是不需要的，p()的作用是最后用来“逆推”出最短路径！）2. 取最小的D()值那个节点，我们“假装”认为它是最短的距离。PS：这里书上说添到一个新的集合中，其实我觉得为了达到算法目的，不要这个集合也行，只要做到以下两点：（1） 下一行选最小D()值时不把之前选过的节点考虑在内（2） 每一行D()的更新只需要做到对剩下每一个D()检查一次更新即可3. 到新的一行（也就是每次循环）就对剩下（还没有选过的节点）的D()做一个检查更新，方法也很简单：假设源节点为A，目标节点为B，上一行（循环）选中的节点为C，那么 D(B) = min D(B), distance(C,B)+D(C) 4. 重复2、3步骤（循环）循环何时终止呢？大家看表4-3就会明白循环次数就是节点的个数5. 得到了最短距离后如何得到最短路径呢？这个时候p()就派上用场了，方法也很简单，逆推即可：设源节点是A，目标节点是B，路径就该是B p(B) p(p(B) AB 知道了Dijkstra算法的设计思想后，怎么编程呢？！我们编程最容易遇到的问题莫过于此：一个算法用数学语言或者人类自然语言比较容易描述和理解，但是代码（机器语言）却很难把简单的一段话实现，但是如果按照前面讲过的几个要点依次来编写就是很容易的，这里就谈谈关键的几个步骤吧：1. “图”的绘制想必大家都是手工输入节点和任意两条边间的距离吧？不说太夸张的，如果我有15个节点，有50条边，估计手指按键盘都得按疼（100个节点，300条边更不说了）这里，我听取了学长的建议，无论是节点的名称、节点的个数、源节点的选取还是边的权值都用系统随机数设置（这里比如还可以设随到-1的话表示无穷大）这就是全自动化的好处，再也不用担心手疼了！因此，我选择使用JAVA里的随机类Random，一方面是方便省心省力另一方面“All Random”（全随机）更能帮你检查算法正确性以及更加符合实际2. 选D()最小值：自己写一个求数组最小值的min()函数就可以了，每次求D()最小值是要排除已经选过的节点的，怎么实现呢？可以把选过的节点的D()值用另一个数组的元素暂存起来，然后自己被赋成，这样minD(Vi)就不会出现重复了3. D()值更新其实也就是算法最精华的部分，采用判断语句就可以了：数学表达：D(B) = min D(B), distance(C,B)+D(C) 代码表达：Di=Didiski+Dk?Di:diski+Dk或者if+else语句也行4. 最佳路径的查找也就是迭代我们可以使用while语句进行，终止条件就是迭代得到的节点是源节点就可以了，例如目标节点是D，源节点是A那么由p(D)得到了C，再由p(C)得到B，再有p(B)得到A，迭代终止我们可以以此得到DCBA，颠倒顺序就可以得到最短路径ABCD了！7. 类概览与描述（1） Grap类：自定义的“图”类，用于模拟各个路由器（节点）和各条链路（边），主要功能函数如下：Public Grap(Stringv)自定义的构造函数，主要功能有：A 接收随机定义好的（名字和数量都是由系统随机指定的）顶点集B 对顶点集经行初始化并且初始化任意两个定点间的距离值（如果不可直达则为无穷大），这里的距离值（即权值）是由系统随机数指定的C 依次显示路由器数量、名称、各路由器到其他路由器的距离值D 统计非无穷大边（有限权值边）的数量并显示（2） Dijkstra类：主函数类，实现核心功能，主要功能函数有：A Public static int min(int a)最小值函数，获取一个指定的整型数组中最小值对应的数组下标B Public static String closestpath(String route,String p,int star)路径计算函数，该函数是建立在已经计算得到最小距离之上的，用字符串数组依次保存源节点到各目标节点的最短路径上的路由器名称C Public static void dijkstra(Grap g,String star)Dijkstra算法中求找最小距离的功能函数，运行结果依次显示源节点到各目标节点的最小距离和对应的最短路径D Public static void main(String args)主函数，用于程序的初始化（比如随机顶点集的初始化）和程序算法的执行（调用各功能函数）8. 代码展示与描述（一） Grap类import java.util.Random;public class Grap String route;int distance;int count=0;public Grap(Stringv)route=v;/获取顶点集distance=new introute.lengthroute.length;/用二维数组保存任意两条边的距离System.out.print(【随机】设置了+v.length+个路由器 );/统计路由器总数System.out.print(路由名分别为： );for(int i=0;iv.length;i+)System.out.print(vi);System.out.print( );/依次显示路径名称System.out.println();for(int i=0;iroute.length;i+)distanceii=0;/设置自己到自己的距离为0for(int i=0;iroute.length-1;i+)System.out.print(【随机】路由+routei+到其他路由的距离依次为： );for(int j=i+1;j100)/设置一定的概率出现“无穷大”distanceij=10000;System.out.print( );distanceji=distanceij;elsedistanceij=ran;System.out.print( );System.out.print(ran);/依次显示每个顶点到其他顶点的距离distanceji=ran;count+;System.out.println();System.out.print(【统计】本架构中总共有： );/统计有限权值边的条数System.out.print(count);System.out.print( 条边！ );（二） Dijkstra类import java.util.Random;public class Dijkstra public static int min(int a)/返回数组中的最小值的下标int min=a0;int minsign=0;for(int i=0;ia.length;i+)if(ai!=0)if(aimin)min=ai;minsign=i;return minsign;/min表示最小值，minsign表示对应的元素下标public static String closestpath(String route,String p,int star)/计算各条最短路径并且保存于字符串数组中int num=route.length;/获取节点数int sorce=star;/获取源节点String vname=route;/获取顶点集String path=new Stringnum;/路径for(int i=0;inum;i+)pathi=vnamei+ ;String p1=AB;for(int i=0;inum;i+)if(i!=sorce)p1=pi; /采用逆推思维，从后向前依次表示pathi+=p1+ ;while( p1!=null&(!p1.equals(vnamesorce) )/逆推至源节点表示最短路径完全确定了for(int t=0;tnum;t+)if(vnamet.equals(p1)p1=pt;pathi+=p1+ ;String path01=new Stringnum;/以下部分均是路径显示格式的调整与转换String truepath=new Stringnum;for(int i=0;inum;i+) truepathi=;for(int i=0;inum;i+)path01i=pathi.split( );for(int i=0;inum;i+)path01ipath01i.length-1=routesorce;for(int i=0;i=0;j-)if(path01ij!=null)truepathi+=path01ij+ ;for(int i=0;inum;i+)truepathi=truepathi.replaceAll( , );truepathi=truepathi.substring(0,truepathi.length()-1);return truepath;public static void dijkstra(Grap g,String star)/获取源节点到各节点最小距离的算法int vnum=g.route.length;/获取节点数String source=star;/获取源节点String v=g.route; /获取顶点集int dis=g.distance; /获取任意两点间距离值（权值）int sorce;for(sorce=0;sorcevnum;sorce+)if(vsorce.equals(source)break;/锁定源节点intD=new intvnum;/用来表示源节点到目标节点当前的最短距离Stringp=new Stringvnum;/表示源节点到目标节点当前最短路径上的前一节点int closest=new intvnum;/存放最短距离for(int i=0;ivnum;i+) closesti=10000;closestsorce=0;for(int i=0;ivnum;i+)if(i!=sorce)Di=dissorcei;/初始化dijkstra算法表第一行pi=source;Dsorce=10000;int sv=1;/标志当前已经纳入集合的节点个数while(svvnum)int sign=min(D);/获取所有距离值中最小的一个的路由器下标sv+;/把该节点加入到集合中；for(int i=0;idissigni+Dsign)Di=dissigni+Dsign; /更新最小距离的表pi=vsign;/更新最短路径的前一个节点closestsign=Dsign;Dsign=9999;String closestpath=closestpath(v,p,sorce); /在获得了最小距离后，立刻求找对应的最短距离for(int i=0;ivnum;