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

江 西 理 工 大 学

数据结构

图的最短路径问题

专业班级 计算机(中加)131班 学号

1520133713

同组人

地点 信息学院621 单独完成

实验报告

pathInfo.put(child.getName(),

pathInfo.get(nearest.getName())+"->"+child.getName()); } } }

computePath(start);//重复执行自己,确保所有子节点被遍历 computePath(nearest);//向外一层层递归,直至所有顶点被遍历 }

public void printPathInfo(){

Set<Map.Entry<String, String>> pathInfos=pathInfo.entrySet(); for(Map.Entry<String, String> pathInfo:pathInfos){

out.println(pathInfo.getKey()+":"+pathInfo.getValue()); } } /**

* 获取与node最近的子节点 */

private Node getShortestPath(Node node){ Node res=null;

int minDis=Integer.MAX_VALUE;

Map<Node,Integer> childs=node.getChild();

实验名称

日期 2014-12-8 实验人 王鹏伟

一、 实验目的

1、 按照老师要求实现对图最短路径的求解问题； 2、 掌握Dijkstra's算法。 二、 实验要求

1、对一个给定的图，求出其中一点到各点的最短路径 三、实验内容

for(Node child:childs.keySet()){ 1、利用书本14.3.1 theory：Dijkstra's algorithm以及上课老师PPT所讲的知识解决问题，

并输出结果。 四、实验过程和结果

部分实验代码：

public void computePath(Node start){

Node nearest=getShortestPath(start);//取距离start节点最近的子节点,放入close if(nearest==null){ return; }

close.add(nearest); open.remove(nearest);

Map<Node,Integer> childs=nearest.getChild(); for(Node child:childs.keySet()){

if(open.contains(child)){//如果子节点在open中

Integer newCompute=path.get(nearest.getName())+childs.get(child); if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离

path.put(child.getName(), newCompute);

if(open.contains(child)){

int distance=childs.get(child); if(distance<minDis){ minDis=distance; res=child; } } }

return res;

}

过程细节请调试源代码！

原图：

数据库系统

实验报告

第2 页/ 共2页

实验结果：

五、实验总结

最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的路 径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完 毕后回溯找到每个顶点的最短路径和权重。

虽然这个程序不是我自己写的，它是我从百度是搜索的，但是，通过我一点一点的看代码，分析代码，运行代码，我也算是搞懂了其中的思想。正如老师所说，当你不会的时候，就将在网上down下来的代码好好的多看几遍，不懂得地方据多问问，这也是一种学习方法。