一、实验目的
通过本实验的学习理解了Dijkstra算法，并对最短路径问题进行了编码实现。
二.实验内容
本Dijkstra算法的实验采用java实现，因此解决方案也使用了java中的接口，有map映射和set集合。
戴克斯特拉算法是一种利用广度优先搜索解决加权有向图或有向图单源最短路径问题的贪婪算法，其目的是求解从其他节点到源的最短路径。 该算法不能计算负加权有向图或有向图。
戴克斯特拉法采用了贪婪策略，即利用Map对象path存储各节点名和从该节点到相邻节点的距离，利用set集合存储找到最短路径的节点的集合close，利用set对象open存储未处理节点的集合在初始情况下，原点a的路径权重指定为0。 同时设置所有其他(a无法直接到达)节点的路径长度MAX_VALUE。 在初始情况下，close中只有节点s。 接着，扫描来自节点a的所有节点，并选出来自a节点的最短的密钥值来代替a节点。 我把这个最短距离储存在path里。 接着，新添加的节点是否能够到达其他顶点，通过该节点到达其他点的路径的长度是否比a点直接到达的短，如果是，则需要置换这些顶点在PATH中的值。 然后，寻找下一个背面节点的最近的key值，重复上述动作直到close包含了图的所有顶点。
三.实验要求
对下图中从顶点a到其中一个顶点的最短路径进行编码。
四.实验过程
1、工艺分析
首先，使用继承Map接口的HashMap类来存储图中的信息。 其中key是图中每个节点的名称，value是每个节点与对应节点之间的连接权重。 另一方面，Map对象Path存储从a节点到每个子节点的权重及其节点的名称，而另一个Map对象child存储从每个节点到相邻节点的权重及其节点的名称，以及Map对象PathInfo
然后开始实现Dijkstra算法。 此代码封装了一个Dijkstra类，其中包含三种方法： getshortestPath、computPath和PrintPathInfo .
yxdggx、getshortestPath方法是为了求出最短路径，他返回的是节点，给这个类实参，即节点，检查循环图中还留在open中的节点，利用以前保存在child中的权重信息其重要过程是将当前的距离与minDis进行比较。 距离越小，则被分配给minDis；随着扫描的进行，minDis继续被分配；扫描结束，minDis的值为最短距离，相应的key值是最接近被称为实参的节点的子节点。
computPath方法用于计算节点之间的距离。 该方法的重要过程首先使用上面的getshortestPath方法获取最接近前面的源点的子节点nearst，然后根据该节点确定从open中的节点到a点的路径newCompute 如果名为newCompute的值小于存储在Path中的open节点与a节点之间的距离，请用此newCompute替换Path值，同时更新PathInfo值。 这里，newCompute的求出方法是，在对应于Path中的nearst节点的权重上加上从child中的该open中的节点到nearst的权重。 该类通过递归地实现Path中的value，不断给更小的值赋值，得到最终的最短路径。
PrintPathInfo方法用于打印路径信息，并打印PathInfo的键值。
2、实验结果
五.实验总结
关于戴克斯特拉法，刚开始做的时候有很大的阻力，但是为了更好地理解这个算法的思想，从网上找了四五个关于这个算法的例子，持续模拟了解决过程，结果得到了戴克斯特拉法的精髓这个过程花了很长时间。 之后，我们用代码实现了它。 该算法涉及键-值对。 正好java语言有一个Map接口，所以我们选择了java作为基本语言来实现这个戴克斯特拉算法。 其中，也非常辛苦。 幸运的是，java对set的集合、Map接口的子类以及他们的方法更了解。 通过这次实验，我们不仅更加详细了
感谢教我本实验的老师。 我得到了吸收这样知识的机会。 只是，我们自己只是有很多漏洞，需要进一步学习。
附录(源代码)
package cn.sal.lisan；
import java.util.HashMap；
import java.util.HashSet；
import java.util.Map；
import java.util.Set；
import cn.sal.Lisan2.MapBuilder；
import cn.sal.Lisan2.Node；
类节点{
私有字符串名称；
private Map child=new HashMap
gt;();public Node(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;
}
}
class MapBuilder {
public Node build(Set open, Set close){
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类里的getchild()方法，再利用散列映射的put方法，将其他节点和权值关联后添加进去
nodeA.getChild().put(nodeB, 6);
nodeA.getChild().put(nodeC, 3);
nodeB.getChild().put(nodeA, 6);
nodeB.getChild().put(nodeC, 2);
nodeB.getChild().put(nodeD, 5);
nodeC.getChild().put(nodeA, 3);
nodeC.getChild().put(nodeB, 2);
nodeC.getChild().put(nodeD, 3);
nodeC.getChild().put(nodeE, 4);
nodeD.getChild().put(nodeB, 5);
nodeD.getChild().put(nodeC, 3);
nodeD.getChild().put(nodeF, 3);
nodeD.getChild().put(nodeE, 2);
nodeE.getChild().put(nodeC, 4);
nodeE.getChild().put(nodeD, 2);
nodeE.getChild().put(nodeF, 5);
nodeF.getChild().put(nodeD, 3);
nodeF.getChild().put(nodeE, 5);
open.add(nodeB);
open.add(nodeC);
open.add(nodeD);
open.add(nodeE);
open.add(nodeF);
close.add(nodeA);
return nodeA;
}
}
class Dijkstra {
Set open = new HashSet();
Set close = new HashSet();
Map path = new HashMap();//封装路径距离
Map pathInfo = new HashMap();//封装路径信息
public Node init() {
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 6);
pathInfo.put("B", "A->B");
path.put("C", 3);
pathInfo.put("C", "A->C");
path.put("D", Integer.MAX_VALUE);
pathInfo.put("D", "A->D");
path.put("E", Integer.MAX_VALUE);
pathInfo.put("E", "A");
path.put("F", Integer.MAX_VALUE);
pathInfo.put("F", "A->F");
//将初始节点放入close,其他节点放入open
Node start = new MapBuilder().build(open, close);
return start;
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node) {
Node res = null;
int minDis = Integer.MAX_VALUE;
Map childs = node.getChild();
// 遍历与Node相连接的所有节点，选取其中距离最短的节点
for (Node child : childs.keySet()) {//keyset()方法用来返回键即节点
if (open.contains(child)) {
int distance = childs.get(child);
if (distance < minDis) {
minDis = distance;
res = child;
}
}
}
return res;
}
/*
* 计算路径
*
*
*
*/
public void computePath(Node start) {
//取距离start节点最近的子节点,放入close
Node nearest = getShortestPath(start);
if (nearest == null) {
return;
}
close.add(nearest); //已遍历的
open.remove(nearest); //未遍历的
Map childs = nearest.getChild();//getChild()返回child 对象，
//child中存储了各节点到相邻节点的距离·
for (Node child : childs.keySet()) {//遍历最近的节点
if (open.contains(child)) {//如果子节点在open中
Integer newCompute = path.get(nearest.getName()) + childs.get(child);
//Map接口的get()方法用来返回key所对应的value，
//此句是用来计算neareset这个节点到每个子节点的距离
if (newCompute < path.get(child.getName())) {
//新计算出来的距离小于之前设置的距离
path.put(child.getName(), newCompute);
pathInfo.put(child.getName(), pathInfo.get(nearest.getName()) + "->" + child.getName());
}
//本if语句可以用来更新A到子节点的最短距离
}
}
computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo() {
//entrySet()返回此映射中包含的映射关系的set视图
Set> pathInfos = pathInfo.entrySet();
for (Map.Entry pathInfo : pathInfos) {
System.out.println(pathInfo.getKey() + ":" + pathInfo.getValue());
}
}
}
public class DijkstraTest {
public static void main(String args[]) throws Exception {
Dijkstra test=new Dijkstra();
Node start=test.init();
test.computePath(start);
test.printPathInfo();
}
}