数据结构--图的最短路径.doc

《数据结构--图的最短路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江西理工大学数据结构实验报告实验名称图的最短路径问题日期2014-12-8专业班级计算机(中加)131班地点信息学院621实验人王鹏伟学号同组人单独完成一、实验目的1、按照老师要求实现对图最短路径的求解问题；2、掌握Dijkstra's算法。二、实验要求1、对一个给定的图，求出其中一点到各点的最短路径三、实验内容1、利用书本14.3.1theory：Dijkstra'salgorithm以及上课老师PPT所讲的知识解决问题，并输出结果。四、实验过程和结果部分实验代码：publicvoidcomputePath(Nodestart){Nodenearest=getSho

2、rtestPath(start);//取距离start节点最近的子节点,放入closeif(nearest==null){return;}close.add(nearest);open.remove(nearest);Mapchilds=nearest.getChild();for(Nodechild:childs.keySet()){if(open.contains(child)){//如果子节点在open中IntegernewCompute=path.get(nearest.getName())+childs.get(child);if

3、(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离path.put(child.getName(),newCompute);pathInfo.put(child.getName(),pathInfo.get(nearest.getName())+"->"+child.getName());}}}computePath(start);//重复执行自己,确保所有子节点被遍历computePath(nearest);//向外一层层递归,直至所有顶点被遍历}publicvoidprintPathInfo(){S

4、et>pathInfos=pathInfo.entrySet();for(Map.EntrypathInfo:pathInfos){System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());}}/***获取与node最近的子节点*/privateNodegetShortestPath(Nodenode){Noderes=null;intminDis=Integer.MAX_VALUE;Mapchi

5、lds=node.getChild();for(Nodechild:childs.keySet()){if(open.contains(child)){intdistance=childs.get(child);if(distance

6、就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。虽然这个程序不是我自己写的，它是我从百度是搜索的，但是，通过我一点一点的看代码，分析代码，运行代码，我也算是搞懂了其中的思想。正如老师所说，当你不会的时候，就将在网上down下来的代码好好的多看几遍，不懂得地方据多问问，这也是一种学习方法。