java实现Dijkstra最短路径算法

public class node {

  private string name;

  private map<node,integer> child= new hashmap<node,integer>();

  public node(string name){

  this .name=name;

  }

  public string getname() {

  return name;

  }

  public void setname(string name) {

  this .name = name;

  }

  public map<node, integer> getchild() {

  return child;

  }

  public void setchild(map<node, integer> child) {

  this .child = child;

  }

}

public class mapbuilder {

  public node build(set<node> open, set<node> 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 nodeg= new node( "g" );

  node nodeh= new node( "h" );

  nodea.getchild().put(nodeb, 1 );

  nodea.getchild().put(nodec, 1 );

  nodea.getchild().put(noded, 4 );

  nodea.getchild().put(nodeg, 5 );

  nodea.getchild().put(nodef, 2 );

  nodeb.getchild().put(nodea, 1 );

  nodeb.getchild().put(nodef, 2 );

  nodeb.getchild().put(nodeh, 4 );

  nodec.getchild().put(nodea, 1 );

  nodec.getchild().put(nodeg, 3 );

  noded.getchild().put(nodea, 4 );

  noded.getchild().put(nodee, 1 );

  nodee.getchild().put(noded, 1 );

  nodee.getchild().put(nodef, 1 );

  nodef.getchild().put(nodee, 1 );

  nodef.getchild().put(nodeb, 2 );

  nodef.getchild().put(nodea, 2 );

  nodeg.getchild().put(nodec, 3 );

  nodeg.getchild().put(nodea, 5 );

  nodeg.getchild().put(nodeh, 1 );

  nodeh.getchild().put(nodeb, 4 );

  nodeh.getchild().put(nodeg, 1 );

  open.add(nodeb);

  open.add(nodec);

  open.add(noded);

  open.add(nodee);

  open.add(nodef);

  open.add(nodeg);

  open.add(nodeh);

  close.add(nodea);

  return nodea;

  }

}

public class dijkstra {

  set<node> open= new hashset<node>();

  set<node> close= new hashset<node>();

  map<string,integer> path= new hashmap<string,integer>(); //封装路径距离

  map<string,string> pathinfo= new hashmap<string,string>(); //封装路径信息

  public node init(){

  //初始路径,因没有a->e这条路径,所以path(e)设置为integer.max_value

  path.put( "b" , 1 );

  pathinfo.put( "b" , "a->b" );

  path.put( "c" , 1 );

  pathinfo.put( "c" , "a->c" );

  path.put( "d" , 4 );

  pathinfo.put( "d" , "a->d" );

  path.put( "e" , integer.max_value);

  pathinfo.put( "e" , "a" );

  path.put( "f" , 2 );

  pathinfo.put( "f" , "a->f" );

  path.put( "g" , 5 );

  pathinfo.put( "g" , "a->g" );

  path.put( "h" , integer.max_value);

  pathinfo.put( "h" , "a" );

  //将初始节点放入close,其他节点放入open

  node start= new mapbuilder().build(open,close);

  return start;

  }

  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);

    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){

   system.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();

  for (node child:childs.keyset()){

   if (open.contains(child)){

   int distance=childs.get(child);

   if (distance<mindis){

    mindis=distance;

    res=child;

   }

   }

  }

  return res;

  }

}

public class main {

  public static void main(string[] args) {

  dijkstra test= new dijkstra();

  node start=test.init();

  test测试数据putepath(start);

  test.printpathinfo();

  }

}