网络原理实验报告
——编程实现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 = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infty 7 Loop
8 find w not in N such that D(w) is a minimum 9 add w to N
10 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 known 13 shortest path cost to w plus cost from w to v */ 14 until all nodes in N
4. 实验步骤
（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()做一个检查更新，方法也很简单：
