网络原理实验报告(Dijkstra)

《网络原理实验报告(Dijkstra)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、网络原理实验报告编程实现Dijkstra路由算法姓名:班级:学号:教师:1•实验目的运用各种编程语言实现基于Dijkstra算法的路由软件。PS：这里使用的是JAVA语言2•实验意义通过本实验，使学生能够对路由原理和路由算法有进一步的理解和掌握。1•实验背景DIJKSTRA算法描述如下：込c(i,j):结点i至结点j之间链路的代价，若i,j不直接相连，则为无穷大。D(v):当前从源结点至目的结点V之间路由的代价。p(v):从源结点至目的结点V之间路由中V之前的结点N:已经知道最优路径的结点集合1Initialization:3forallnodesv4ifvadjacenttoA

2、5thenD(v)=c(A,v)6elseD(v)=infty7Loop8findwnotinNsuchthatD(w)isaminimum9addwtoN10updateD(v)forallvadjacenttowandnotinN:11D(v)=min(D(v),D(w)+c(w,v))12/*newcosttoviseitheroldcosttovorknown13shortestpathcosttowpluscostfromwtov*/14untilallnodesinN1•实验步骤(1)选择合适的编程语言编程实现基于Dijkstra算法的路由软件。(2)输入不同的网络拓

3、扑和链路代价测试和验证自己的路由软件。2•实验环境(1)实验语言：JAVA(2)实验平台：Eclipse(3)引用库函数：随机(Random)库3•算法思想理解与描述在编写代码时，我曾遇到过两个问题也是最容易碰到的难题,这里我介绍一下自己的解决方法：Dijkstra算法究竟是怎样计算最短距离和最短路径的?也许如果只是要我们写一个算法，求最短路径和最小距离，那么我们可能不同的人有不同的“自然而然”的思路，而且肯定很多并不与Dijkstra算法雷同，但令我们头疼的是:这里是别人写好了一个算法，我们得去理解，而不是让我们自己去操刀。在我看来，与其看那些枯燥无味的算法文字叙述还不如看图看

4、表我就是看了(中文版)P240的表4-3(它对应着P238的图4-27)才明白是“怎么算的”，这里我就说下自己的理解，也不过就是几句话而已：1.一开始，将源节点到各点的直达距离作为最短距离;PS：这里还是要理解表中DO和p()的含义一一D()就是刚才说的到目标节点的“目前认为”的最短距离，而p()是“当前认为”的最短路径上到目标节点的前一节点(至少我是这么认为的：如果只求最短距离，p()是不需要的，p()的作用是最后用来“逆推”出最短路径！)2.取最小的D()值那个节点，我们“假装”认为它是最短的距离。PS：这里书上说添到一个新的集合中，其实我觉得为了达到算法目的，不要这个集合也

5、行，只要做到以下两点:(1)下一行选最小D()值时不把之前选过的节点考虑在内(2)每一行D()的更新只需要做到对剩下每一个D()检查一次更新即可3.到新的一行(也就是每次循环)就对剩下(还没有选过的节点)的D()做一个检查更新，方法也很简单:假设源节点为A,目标节点为B,上一行(循环)选中的节点为C,那么D(B)=min{D(B),distance(C,B)+D(C)}1.重复2、3步骤(循环)一一循环何时终止呢？大家看表4-3就会明白循环次数就是节点的个数2.得到了最短距离后如何得到最短路径呢？这个时候p()就派上用场了，方法也很简单，逆推即可：设源节点是A,目标节点是B,路径

6、就该是B—p(B)—p(p(B))——AB.知道了Dijkstra算法的设计思想后，怎么编程呢？！我们编程最容易遇到的问题莫过于此：一个算法用数学语言或者人类自然语言比较容易描述和理解，但是代码(机器语言)却很难把简单的一段话实现，但是如果按照前面讲过的几个要点依次来编写就是很容易的，这里就谈谈关键的几个步骤吧：1.“图”的绘制一一想必大家都是手工输入节点和任意两条边间的距离吧？不说太夸张的，如果我有15个节点,有50条边，估计手指按键盘都得按疼(100个节点，300条边更不说了)这里，我听取了学长的建议，无论是节点的名称、节点的个数、源节点的选取还是边的权值都用系统随机数设置(

7、这里比如还可以设随到-1的话表示无穷大)一—这就是全自动化的好处，再也不用担心手疼了！因此，我选择使用JAVA里的随机类Random,一方面是方便省心省力另一方面"AllRandom"(全随机)更能帮你检查算法正确性以及更加符合实际1.选D()最小值：自己写一个求数组最小值的min()函数就可以了，每次求D()最小值是要排除已经选过的节点的,怎么实现呢？一一可以把选过的节点的D()值用另一个数组的元素暂存起来，然后自己被赋成8,这样min{D(Vi)}就不会岀现重复了2.D()值