算法设计与分析基础上机实验3

算法分析与设计

学 院 学 号 姓 名 指 导 教 师 使 用 教 材 算法设计与分析基础 编 写 时 间

1/4

实验3图搜索及最短路径实验

实验目的： （1） 掌握图算法的思想，熟练掌握图算法的经典求解问题。 （2） 编写代码实现图算法中的搜索算法及最短路径算法。 实验内容： Ex1：用伪代码描述Dijkstra算法并实现。用程序分别实现求解加权无向图和加权有向图的Dijkstra算法（分别用P260习题9.3的2b,2a进行验证）。 Ex1算法描述： Dijkstra算法是按照从给定顶点到图中每一个其他顶点的最短赋权路径 步骤：1.找出给定顶点到邻接顶点中的权最小的 2.更新该顶点的邻接顶点的权重 3.重复步骤1和2，直到图中所有顶点都被访问 4.输出最终路径 算法（参照书p259的伪代码） Dijkstra（G,w,s） //单起点最短路径的Dijkstra算法 //输入：具有非负权重加权连通图G=以及它的顶点 //输出：对于V中的每个顶点v来说，从s到v的最短路径长度d，以及路径上的倒数第二个顶点p Q← ø //初始化顶点优先队列 for each vertex v in V[G] dv←0 pv←null Insert(Q,v,dv) //初始化优先队列中顶点的优先级 ds←0 VT←ø Decrease(Q,s,ds) //将s的优先级更新为ds for i←0 to |V|-1 do u*←DeleteMin(Q) //删除优先级最小的元素 VT←VT+{u*} for V-VT中每一个和u*相邻的顶点u do if du*+w(u*,u)int[] shortest = new int[mVx.length]; int[] visited = new int[mVx.length]; String[] path = new String[mVx.length]; for (int i = 0; i < mVx.length; i++) { path[i] = new String(source + \"->\" + i); } shortest[source] = 0; visited[source] = 1; for (int i = 1; i < mVx.length; i++) { int min = Integer.MAX_VALUE; int index = -1; for (int j = 0; j < mVx.length; j++) { if (visited[j] == 0 && mVx[source][j] < min) { min = mVx[source][j]; index = j; } } shortest[index] = min; visited[index] = 1; for (int m = 0; m < mVx.length; m++) { if (visited[m] == 0 && mVx[source][index] +mVx[index][m] \" + m; } } for (int i1 = 0; i1 < mVx.length; i1++) { if (i1 != source) { if (shortest[i1] == MaxValue) { System.out.println(source + \"到\"+i1+ \"不可达\"); } else { System.out.println(source + \"到\"+i1+ \"的最短路径为：\" + path[i1] + \"，最短距离是：\" + shortest[i1]); } } } } } 运行（测试）过程及结果： 9.3的2b 3/4

2a 总结：

4/4