算法分析与设计实验二

《算法分析与设计实验二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法分析与设计》实验报告专业：计科班级：日期：2016/04/11成绩:学生姓名：学号：指导老师：实验单元二动态规划一、实验题目实验一最短路径二、实验目的熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。三、实验内容通过对最短路径求解的学习，掌握动态规划算法的基本思想，能根据邻接矩阵或邻接链表求解。实验描述：在一个无向图中，获取起始节点到所有其他节点的最短路径描述实验基本思想：Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终

2、点为止。用openSet,closeSet集合方式，其采用的是贪心算法策略，大概过程如下：1.声明两个集合，openSet和closeSet，openSet用于存储未遍历的节点，closeSet用来存储已遍历的节点2.初始阶段，将初始节点放入closeSet，其他所有节点放入openSet3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入closeSet并从新计算路径，直至closeSet包含所有子节点实验相关无向图：四、实验结果（代码及运行结果）实验源代码：7Node.java文件（描述节点属性）importjava.util.HashMap;importjava.uti

3、l.Map;publicclassNode{privateStringname;//节点名称privateMapchild=newHashMap();//建立Map节点publicNode(Stringname){//构造函数完成名称的初始化this.name=name;}publicStringgetName(){returnname;}publicvoidsetName(Stringname){this.name=name;}publicMapgetChild(){//获取孩子节点（下一个节点）retu

4、rnchild;}publicvoidsetChild(Mapchild){//设置孩子节点this.child=child;}}MapBuilder.java文件（完成链表节点的建立）importjava.util.Set;/***建立映射*完成无向图中定点之间的关系以及边的长度的建立*/publicclassMapBuilder{publicNodebuild(SetopenSet,SetcloseSet){//初始化无向图的各个顶点NodenodeA=newNode("A");NodenodeB=newNode("B");Noden

5、odeC=newNode("C");NodenodeD=newNode("D");NodenodeE=newNode("E");NodenodeF=newNode("F");NodenodeG=newNode("G");NodenodeH=newNode("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);7nodeA.getChild().pu

6、t(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的路径长度nod

7、eE.getChild().put(nodeD,1);nodeE.getChild().put(nodeF,1);//设置F到孩子节点A、B、E的路径长度nodeF.getChild().put(nodeA,2);nodeF.getChild().put(nodeB,2);nodeF.getChild().put(nodeE,1);//设置G到孩子节点A、C、H的路径长度nodeG.getChild().put(node