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

网络原理实验报告——编程实现Dijkstra路由算法姓名： 班级：学号：教师： 实验目的运用各种编程语言实现基于Dijkstra算法的路由软件。PS：这里使用的是JAVA语言实验意义通过本实验，使学生能够对路由原理和路由算法有进一步的理解和掌握。实验背景Dijkstra算法描述如下：设：c(i,j): 结点i至结点j之间链路的代价，若i,j不直接相连，则为无穷大。D(v): 当前从源结点至目的结点V之间路由的代价。p(v): 从源结点至目的结点V之间路由中V之前的结点N: 已经知道最优路径的结点集合1 Initialization:2 N = {A}3 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 N实验步骤选择合适的编程语言编程实现基于Dijkstra算法的路由软件。输入不同的网络拓扑和链路代价测试和验证自己的路由软件。实验环境实验语言：JAVA实验平台：Eclipse引用库函数：随机（Random）库算法思想理解与描述在编写代码时，我曾遇到过两个问题也是最容易碰到的难题，这里我介绍一下自己的解决方法：Dijkstra算法究竟是怎样计算最短距离和最短路径的？也许如果只是要我们写一个算法，求最短路径和最小距离，那么我们可能不同的人有不同的“自然而然”的思路，而且肯定很多并不与Dijkstra算法雷同，但令我们头疼的是：这里是别人写好了一个算法，我们得去理解，而不是让我们自己去操刀。在我看来，与其看那些枯燥无味的算法文字叙述还不如看图看表——我就是看了（中文版）P240的表4-3（它对应着P238的图4-27）才明白是“怎么算的”，这里我就说下自己的理解，也不过就是几句话而已：一开始，将源节点到各点的直达距离作为最短距离；PS：这里还是要理解表中D()和p()的含义——D()就是刚才说的到目标节点的“目前认为”的最短距离，而p()是“当前认为”的最短路径上到目标节点的前一节点（至少我是这么认为的：如果只求最短距离，p()是不需要的，p()的作用是最后用来“逆推”出最短路径！）取最小的D()值那个节点，我们“假装”认为它是最短的距离。PS：这里书上说添到一个新的集合中，其实我觉得为了达到算法目的，不要这个集合也行，只要做到以下两点：（1） 下一行选最小D()值时不把之前选过的节点考虑在内（2） 每一行D()的更新只需要做到对剩下每一个D()检查一次更新即可到新的一行（也就是每次循环）就对剩下（还没有选过的节点）的D()做一个检查更新，方法也很简单：假设源节点为A，目标节点为B，上一行（循环）选中的节点为C，那么 D(B) = min{ D(B), distance(C,B)+D(C) }重复2、3步骤（循环）——循环何时终止呢？大家看表4-3就会明白循环次数就是节点的个数得到了最短距离后如何得到最短路径呢？这个时候p()就派上用场了，方法也很简单，逆推即可：设源节点是A，目标节点是B，路径就该是B ← p(B) ← p(p(B)) ← …… ← A知道了Dijkstra算法的设计思想后，怎么编程呢？！我们编程最容易遇到的问题莫过于此：一个算法用数学语言或者人类自然语言比较容易描述和理解，但是代码（机器语言）却很难把简单的一段话实现，但是如果按照前面讲过的几个要点依次来编写就是很容易的，这里就谈谈关键的几个步骤吧： “图”的绘制——想必大家都是手工输入节点和任意两条边间的距离吧？不说太夸张的，如果我有15个节点，有50条边，估计手指按键盘都得按疼（100个节点，300条边更不说了）这里，我听取了学长的建议，无论是节点的名称、节点的个数、源节点的选取还是边的权值都用系统随机数设置（这里比如还可以设随到-1的话表示无穷大）——这就是全自动化的好处，再也不用担心手疼了！因此，我选择使用JAVA里的随机类Random，一方面是方便省心省力另一方面“All Random”（全随机）更能帮你检查算法正确性以及更加符合实际 选D()最小值：自己写一个求数组最小值的min()函数就可以了，每次求D()最小