l算法分析与设计实验二.docxVIP

《算法分析与设计》实验报告专业：计科班级：日期：2016/04/11 成绩:学生姓名：学号：指导老师：实验单元二动态规划实验题目实验一最短路径实验目的熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。实验内容通过对最短路径求解的学习，掌握动态规划算法的基本思想，能根据邻接矩阵或邻接链表求解。实验描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述实验基本思想：Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。用openSet, closeSet集合方式，其采用的是贪心算法策略，大概过程如下：1.声明两个集合，openSet和closeSet，openSet用于存储未遍历的节点，closeSet用来存储已遍历的节点2.初始阶段，将初始节点放入closeSet，其他所有节点放入openSet3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入closeSet并从新计算路径，直至closeSet包含所有子节点实验相关无向图：实验结果（代码及运行结果）实验源代码：Node.java文件（描述节点属性）import java.util.HashMap;import java.util.Map;publicclassNode {private String name; // 节点名称private MapNode, Integer child = new HashMapNode, Integer(); // 建立Map节点public Node(String name) { // 构造函数完成名称的初始化 = name;}public String getName() {returnname;}publicvoid setName(String name) { = name;}public MapNode, Integer getChild() { // 获取孩子节点（下一个节点）returnchild;}publicvoid setChild(MapNode, Integer child) { // 设置孩子节点this.child = child;}}MapBuilder.java文件（完成链表节点的建立）import java.util.Set;/** * 建立映射 * 完成无向图中定点之间的关系以及边的长度的建立*/publicclass MapBuilder { public Node build(SetNode openSet, SetNode closeSet){ // 初始化无向图的各个顶点Node nodeA=new Node(A); Node nodeB=new Node(B); Node nodeC=new Node(C); Node nodeD=new Node(D); Node nodeE=new Node(E); Node nodeF=new Node(F); Node nodeG=new Node(G); Node nodeH=new Node(H); // 设置源A到孩子节点B、C、D、F、G的路径长度nodeA.getChild().put(nodeB, 1); nodeA.getChild().put(nodeC, 1); nodeA.getChild().put(nodeD, 4); nodeA.getChild().put(nodeF, 2);nodeA.getChild().put(nodeG, 5); // 设置B到孩子节点A、F、H的路径长度nodeB.getChild().put(nodeA, 1); nodeB.getChild().put(nodeF, 2); nodeB.getChild().put(nodeH, 4); // 设置C到孩子节点A、G的路径长度nodeC.getChild().put(nodeA, 1); nodeC.getChild().put(nodeG, 3); // 设置D到孩子节点A、E的路径长度nodeD.getChild().put(nodeA, 4); nodeD.getChild().put(nodeE, 1);// 设置E到孩子节点D、F的路径长度nodeE.getChild().put(nodeD, 1); nodeE.getChild().put(nodeF, 1);// 设置F到孩子节点A、B、E的路径