假设源节点为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)) ← ?? ← A
B． 知道了Dijkstra算法的设计思想后，怎么编程呢？！
我们编程最容易遇到的问题莫过于此：一个算法用数学语言或者人类自然语言比较容易描述和理解，但是代码（机器语言）却很难把简单的一段话实现，但是如果按照前面讲过的几个要点依次来编写就是很容易的，这里就谈谈关键的几个步骤吧：
1. “图”的绘制——想必大家都是手工输入节点和任意两条边间的距离吧？不说太夸张的，如果我有15个节点，有50条边，估计手指按键盘都得按疼（100个节点，300条边更不说了）
这里，我听取了学长的建议，无论是节点的名称、节点的个数、源节点的选取还是边的权值都用系统随机数设置（这里比如还可以设随到-1的话表示无穷大）——这就是全自动化的好处，再也不用担心手疼了！因此，
我选择使用JAVA里的随机类Random，一方面是方便省心省力另一方面“All Random”（全随机）更能帮你检查算法正确性以及更加符合实际
2. 选D()最小值：自己写一个求数组最小值的min()函数就可以了，每次求D()最小值是要排除已经选过的节点的，怎么实现呢？——可以把选过的节点的D()值用另一个数组的元素暂存起来，然后自己被赋成∞，这样min{D(Vi)}就不会出现重复了
3. D()值更新——其实也就是算法最精华的部分，采用判断语句就可以了：
数学表达：D(B) = min{ D(B), distance(C,B)+D(C) } 代码表达：D[i]=D[i] 或者if+else语句也行 4. 最佳路径的查找——也就是迭代 我们可以使用while语句进行，终止条件就是迭代得到的节点是源节点就可以了，例如目标节点是D，源节点是A那么由p(D)得到了C，再由p(C)得到B，再有p(B)得到A，迭代终止——我们可以以此得到DCBA，颠倒顺序就可以得到最短路径ABCD了！ 7. 类概览与描述 （1） Grap类：自定义的“图”类，用于模拟各个路由器（节 点）和各条链路（边），主要功能函数如下： Public Grap(String[]v)——自定义的构造函数，主要功能有： 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(Grapg,String star)—— Dijkstra算法中求找最小距离的功能函数，运行结果依次显示源节点到各目标节点的最小距离 和对应的最短路径 D． Public static void main(String[] args)——主函数， 用于程序的初始化（比如随机顶点集的初始化）和程序算法的执行（调用各功能函数） 8. 代码展示与描述 （一） Grap类 importjava.util.Random; publicclassGrap { String[] route; int[][] distance; intcount=0; publicGrap(String[]v){ route=v; //获取顶点集 distance=newint[route.length][route.length]; //用二维数组保存任意两条边的距离 System.out.print(\【随机】设置了\+v.length+\个路由器 \); //统计路由器总数 System.out.print(\路由名分别为： \); for(inti=0;i {System.out.print(v[i]);System.out.print(\ \);//依次显示路径名称 System.out.println(); for(inti=0;i
