算法分析与设计实验二

《算法分析与设计实验二》由会员分享，可在线阅读，更多相关《算法分析与设计实验二（7页珍藏版）》请在金锄头文库上搜索。

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

2、想：实验基本思想： Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点 的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 用用 openSet,openSet, closeSetcloseSet 集合方式，其采用的是贪心算法策略，大概过程如下：集合方式，其采用的是贪心算法策略，大概过程如下： 1.声明两个集合，openSet 和 closeSet，openSet 用于存储未遍历的节点，closeSet 用来存 储已遍历的节点 2.初始阶段，将初始节点放入 closeSet，其他所有节点放入 openSet 3.以初始节点为中心向外一

3、层层遍历，获取离指定节点最近的子节点放入 closeSet 并从新 计算路径，直至 closeSet 包含所有子节点实验相关无向图：实验相关无向图：四、四、 实验结果（代码及运行结果）实验结果（代码及运行结果）实验源代码：2Node.javaNode.java 文件（描述节点属性）文件（描述节点属性） import java.util.HashMap; import java.util.Map; public class Node private String name; / 节点名称 private Map child = new HashMap(); / 建立Map节点 public No

4、de(String name) / 构造函数完成名称的初始化 this.name = name; public String getName() return name; public void setName(String name) this.name = name; public Map getChild() / 获取孩子节点（下一个节点） return child; public void setChild(Map child) / 设置孩子节点 this.child = child; MapBuilder.java 文件（完成链表节点的建立）文件（完成链表节点的建立）importim

5、port java.util.Set; /* 建立映射* 完成无向图中定点之间的关系以及边的长度的建立*/ publicpublic classclass MapBuilder publicpublic Node build(Set openSet, Set closeSet) / 初始化无向图的各个顶点Node nodeA=newnew Node(“A“); Node nodeB=newnew Node(“B“); Node nodeC=newnew Node(“C“); Node nodeD=newnew Node(“D“); Node nodeE=newnew Node(“E“); No

6、de nodeF=newnew Node(“F“); Node nodeG=newnew Node(“G“); Node nodeH=newnew 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);3nodeA.getChild().put(nodeG, 5); / 设置B到孩子节点A、F、H的路径长度nodeB.getC

7、hild().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); n

8、odeE.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(nodeA, 5);nodeG.getChild().put(nodeC, 3); nodeG.getChild().put(nodeH, 1);/ 设置H到孩子节点B、G的路径长度nodeH.getChild().put(no

9、deB, 4); nodeH.getChild().put(nodeG, 1);/ 添加B、C、D、E、F、G、H节点到未遍历集合中openSet.add(nodeB); openSet.add(nodeC); openSet.add(nodeD); openSet.add(nodeE); openSet.add(nodeF); openSet.add(nodeG); openSet.add(nodeH);/ 把源A添加到已遍历的集合中closeSet.add(nodeA);returnreturn nodeA; Dijkstra.javaDijkstra.java 文件（核心文件，实现最短路

10、径的查找、路径信息的记录）文件（核心文件，实现最短路径的查找、路径信息的记录）importimport java.util.HashMap; importimport java.util.HashSet; importimport java.util.Map; importimport java.util.Set; /*4* Dijkstra 核心类 实现最短路径的查找以及打印输出*/ publicpublic classclass Dijkstra Set openSet = newnew HashSet(); Set closeSet = newnew HashSet(); Map pat

11、hLen = newnew HashMap(); / 封装路径距离 Map pathInfo = newnew HashMap(); / 封装路径信息 / 初始化节点方法publicpublic Node init() / 初始路径,因没有A-E这条路径,所以path(E)设置为Integer.MAX_VALUEpathLen.put(“B“, 1); pathInfo.put(“B“, “A-B“);pathLen.put(“C“, 1); pathInfo.put(“C“, “A-C“); pathLen.put(“D“, 4); pathInfo.put(“D“, “A-D“); pat

12、hLen.put(“E“, Integer.MAX_VALUEMAX_VALUE); / 无边，设置路径长度为无穷pathInfo.put(“E“, “A“); pathLen.put(“F“, 2); pathInfo.put(“F“, “A-F“); pathLen.put(“G“, 5); pathInfo.put(“G“, “A-G“); pathLen.put(“H“, Integer.MAX_VALUEMAX_VALUE); / 无边，设置路径长度为无穷pathInfo.put(“H“, “A“); / 路径信息建立后，初始化开、闭集合Node start = newnew Map

13、Builder().build(openSet, closeSet); returnreturn start; publicpublic voidvoid computePath(Node start) Node nearest = getShortestPath(start);/ 取距离start节点最近的子节点,放入closeifif (nearest = nullnull) returnreturn; closeSet.add(nearest); / 添加至闭集合中 openSet.remove(nearest); / 从开集合中删除顶点 Map childs = nearest.get

14、Child(); / 获取最近节点的所有子节点 / 循环 遍历查找到的最近节点的所有子节点（childs.keySet()，节点集合）forfor (Node child : childs.keySet() ifif (openSet.contains(child) / 只操作在openSet中的子节点System.outout.println(“childs.get(child):“ + childs.get(child); / childs.get(child)获取节点中存储的距离，对应于MapBuilder中类似于 / nodeF.getChild().put(nodeX, X)语句In

15、teger newCompute = pathLen.get(nearest.getName()5+ childs.get(child); ifif (pathLen.get(child.getName() newCompute) / 之前设置的距离大于新计算 出来的距离pathLen.put(child.getName(), newCompute); pathInfo.put( child.getName(), pathInfo.get(nearest.getName() + “-“ + child.getName(); computePath(start);/ 重复执行自己,确保所有子节点

16、被遍历 computePath(nearest);/ 向外一层层递归,直至所有顶点被遍历 / 打印输出最短路径信息publicpublic voidvoid printPathInfo() Set pathInfos = pathInfo.entrySet(); forfor (Map.Entry pathInfo : pathInfos) System.outout.println(pathInfo.getKey() + “:“ + pathInfo.getValue(); /* 获取与node最近的子节点*/ privateprivate Node getShortestPath(Node node) Node