java如何实现dijkstra最短路径寻路算法

这篇文章将为大家详细讲解有关java如何实现dijkstra最短路径寻路算法,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

做网站、网站建设,成都做网站公司-创新互联公司已向成百上千企业提供了,网站设计,网站制作,网络营销等服务!设计与技术结合,多年网站推广经验,合理的价格为您打造企业品质网站。

迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。 

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

基本思想

通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算)。

此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是"起点s到该顶点的路径"。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。 ... 重复该操作,直到遍历完所有顶点。

操作步骤

(1) 初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"[例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。

(2) 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。

(3) 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。

(4) 重复步骤(2)和(3),直到遍历完所有顶点。

得益于csdn另外一篇博客的算法,我对此做了一些改进。

构建地图:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
 
/**
 * 地图
 * @author jake
 * @date 2014-7-26-下午10:40:10
 * @param  节点主键
 */
public class Maps {
 
 /**
 * 所有的节点集合
 * 节点Id - 节点
 */
 private Map> nodes = new HashMap>();
 
 /**
 * 地图构建器
 * 
 * @author jake
 * @date 2014-7-26-下午9:47:44
 */
 public static class MapBuilder {
 
 /**
  * map实例
  */
 private Maps map = new Maps();
 
 /**
  * 构造MapBuilder
  * 
  * @return MapBuilder
  */
 public MapBuilder create() {
  return new MapBuilder();
 }
 
 /**
  * 添加节点
  * 
  * @param node 节点
  * @return
  */
 public MapBuilder addNode(Node node) {
  map.nodes.put(node.getId(), node);
  return this;
 }
 
 /**
  * 添加路线
  * 
  * @param node1Id 节点Id
  * @param node2Id 节点Id
  * @param weight 权重
  * @return
  */
 public MapBuilder addPath(T node1Id, T node2Id, int weight) {
  Node node1 = map.nodes.get(node1Id);
  if (node1 == null) {
  throw new RuntimeException("无法找到节点:" + node1Id);
  }
 
  Node node2 = map.nodes.get(node2Id);
  if (node2 == null) {
  throw new RuntimeException("无法找到节点:" + node2Id);
  }
 
  node1.getChilds().put(node2, weight);
  node2.getChilds().put(node1, weight);
  return this;
 }
 
 /**
  * 构建map
  * @return map
  */
 public Maps build() {
  return this.map;
 }
 
 }
 
 /**
 * 节点
 * 
 * @author jake
 * @date 2014-7-26-下午9:51:31
 * @param  节点主键类型
 */
 public static class Node {
 
 /**
  * 节点主键
  */
 private T id;
 
 /**
  * 节点联通路径
  * 相连节点 - 权重
  */
 private Map, Integer> childs = new HashMap, Integer>();
 
 /**
  * 构造方法
  * @param id 节点主键
  */
 public Node(T id) {
  this.id = id;
 }
 
 /**
  * 获取实例
  * @param id 主键
  * @return
  */
 public static  Node valueOf(T id) {
  return new Node(id);
 }
 
 /**
  * 是否有效
  * 用于动态变化节点的可用性
  * @return
  */
 public boolean validate() {
  return true;
 }
 
 
 public T getId() {
  return id;
 }
 
 public void setId(T id) {
  this.id = id;
 }
 
 public Map, Integer> getChilds() {
  return childs;
 }
 
 protected void setChilds(Map, Integer> childs) {
  this.childs = childs;
 }
 
 @Override
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append(this.id).append("[");
  for (Iterator, Integer>> it = childs.entrySet().iterator(); it.hasNext();) {
  Entry, Integer> next = it.next();
  sb.append(next.getKey().getId()).append("=").append(next.getValue());
  if (it.hasNext()) {
   sb.append(",");
  }
  }
  sb.append("]");
  return sb.toString();
 }
 
 }
 
 /**
 * 获取地图的无向图节点
 * @return 节点Id - 节点
 */
 public Map> getNodes() {
 return nodes;
 }
 
}

开始寻路:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
 
import com.my9yu.sanguohun2.utils.dijkstra.Maps.MapBuilder;
 
/**
 * 迪杰斯特拉(Dijkstra)图最短路径搜索算法
 * 
每次开始新的搜索需要创建此类对象  * @param  节点的主键类型  * @author jake  * @date 2014-7-26-下午9:45:07  */ public class MapSearcher {    /**  * 最短路径搜索结果类  * @author jake  * @date 2014-7-27-下午3:55:11  * @param  节点的主键类型  */  public static class SearchResult {  /**   * 最短路径结果   */  List path;  /**   * 最短距离   */  Integer distance;    /**   * 获取实例   * @param path 最短路径结果   * @param distance 最短路径距离   * @return   */  protected static  SearchResult valueOf(List path, Integer distance) {   SearchResult r = new SearchResult();   r.path = path;   r.distance = distance;   return r;  }    public List getPath() {   return path;  }  public Integer getDistance() {   return distance;  }    @Override  public String toString() {   StringBuffer sb = new StringBuffer();   sb.append("path:");   for(Iterator it = this.path.iterator(); it.hasNext();) {   sb.append(it.next());   if(it.hasNext()) {    sb.append("->");   }   }   sb.append("\n").append("distance:").append(distance);   return sb.toString();  }    }    /**  * 地图对象  */  Maps map;  /**  * 开始节点  */  Maps.Node startNode;  /**  * 结束节点  */  Maps.Node targetNode;  /**  * 开放的节点  */  Set> open = new HashSet>();  /**  * 关闭的节点  */  Set> close = new HashSet>();  /**  * 最短路径距离  */  Map, Integer> path = new HashMap, Integer>();  /**  * 最短路径  */  Map> pathInfo = new HashMap>();    /**  * 初始化起始点  * 
初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为"起点s到该顶点的距离"  * [例如,U中顶点v的距离为(s,v)的长度,然后s和v不相邻,则v的距离为∞]。  * @param source 起始节点的Id  * @param map 全局地图  * @param closeSet 已经关闭的节点列表  * @return  */  @SuppressWarnings("unchecked")  public Maps.Node init(T source, Maps map, Set closeSet) {    Map> nodeMap = map.getNodes();  Maps.Node startNode = nodeMap.get(source);  //将初始节点放到close  close.add(startNode);  //将其他节点放到open  for(Maps.Node node : nodeMap.values()) {   if(!closeSet.contains(node.getId()) && !node.getId().equals(source)) {   this.open.add(node);   }  }    // 初始路径  T startNodeId = startNode.getId();  for(Entry, Integer> entry : startNode.getChilds().entrySet()) {   Maps.Node node = entry.getKey();   if(open.contains(node)) {   T nodeId = node.getId();   path.put(node, entry.getValue());   pathInfo.put(nodeId, new ArrayList(Arrays.asList(startNodeId, nodeId)));   }  }    for(Maps.Node node : nodeMap.values()) {   if(open.contains(node) && !path.containsKey(node)) {   path.put(node, Integer.MAX_VALUE);   pathInfo.put(node.getId(), new ArrayList(Arrays.asList(startNodeId)));   }  }  this.startNode = startNode;  this.map = map;  return startNode;  }      /**  * 递归Dijkstra  * @param start 已经选取的最近节点  */  protected void computePath(Maps.Node start) {  // 从U中选出"距离最短的顶点k",并将顶点k加入到S中;同时,从U中移除顶点k。  Maps.Node nearest = getShortestPath(start);  if (nearest == null) {   return;  }  //更新U中各个顶点到起点s的距离。  //之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离;  //例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。  close.add(nearest);  open.remove(nearest);  //已经找到结果  if(nearest == this.targetNode) {   return;  }  Map, Integer> childs = nearest.getChilds();  for (Maps.Node child : childs.keySet()) {   if (open.contains(child)) {// 如果子节点在open中   Integer newCompute = path.get(nearest) + childs.get(child);   if (path.get(child) > newCompute) {// 之前设置的距离大于新计算出来的距离    path.put(child, newCompute);      List path = new ArrayList(pathInfo.get(nearest.getId()));    path.add(child.getId());    pathInfo.put(child.getId(), path);   }   }  } // computePath(start);// 重复执行自己,确保所有子节点被遍历  computePath(nearest);// 向外一层层递归,直至所有顶点被遍历  }    /**  * 获取与node最近的子节点  */  private Maps.Node getShortestPath(Maps.Node node) {  Maps.Node res = null;  int minDis = Integer.MAX_VALUE;  for (Maps.Node entry : path.keySet()) {   if (open.contains(entry)) {   int distance = path.get(entry);   if (distance < minDis) {    minDis = distance;    res = entry;   }   }  }  return res;  }    /**  * 获取到目标点的最短路径  *   * @param target  *      目标点  * @return  */  public SearchResult getResult(T target) {  Maps.Node targetNode = this.map.getNodes().get(target);  if(targetNode == null) {   throw new RuntimeException("目标节点不存在!");  }  this.targetNode = targetNode;  //开始计算  this.computePath(startNode);  return SearchResult.valueOf(pathInfo.get(target), path.get(targetNode));  }    /**  * 打印出所有点的最短路径  */  public void printPathInfo() {  Set>> pathInfos = pathInfo.entrySet();  for (Map.Entry> pathInfo : pathInfos) {   System.out.println(pathInfo.getKey() + ":" + pathInfo.getValue());  }  }      /**  * 测试方法  */  @org.junit.Test  public void test() {    MapBuilder mapBuilder = new Maps.MapBuilder().create();  //构建节点  mapBuilder.addNode(Maps.Node.valueOf("A"));  mapBuilder.addNode(Maps.Node.valueOf("B"));  mapBuilder.addNode(Maps.Node.valueOf("C"));  mapBuilder.addNode(Maps.Node.valueOf("D"));  mapBuilder.addNode(Maps.Node.valueOf("E"));  mapBuilder.addNode(Maps.Node.valueOf("F"));  mapBuilder.addNode(Maps.Node.valueOf("G"));  mapBuilder.addNode(Maps.Node.valueOf("H"));  mapBuilder.addNode(Maps.Node.valueOf("I"));  //构建路径  mapBuilder.addPath("A", "B", 1);  mapBuilder.addPath("A", "F", 2);  mapBuilder.addPath("A", "D", 4);  mapBuilder.addPath("A", "C", 1);  mapBuilder.addPath("A", "G", 5);  mapBuilder.addPath("C", "G", 3);  mapBuilder.addPath("G", "H", 1);  mapBuilder.addPath("H", "B", 4);  mapBuilder.addPath("B", "F", 2);  mapBuilder.addPath("E", "F", 1);  mapBuilder.addPath("D", "E", 1);  mapBuilder.addPath("H", "I", 1);  mapBuilder.addPath("C", "I", 1);    //构建全局Map  Maps map = mapBuilder.build();    //创建路径搜索器(每次搜索都需要创建新的MapSearcher)  MapSearcher searcher = new MapSearcher();  //创建关闭节点集合  Set closeNodeIdsSet = new HashSet();  closeNodeIdsSet.add("C");  //设置初始节点  searcher.init("A", map, closeNodeIdsSet);  //获取结果  SearchResult result = searcher.getResult("G");  System.out.println(result);  //test.printPathInfo();  }   }

根据算法的原理可知,getShortestPath是获取open集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则,可以避免路径权重不均导致错寻的情况。

关于“java如何实现dijkstra最短路径寻路算法”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。


新闻标题:java如何实现dijkstra最短路径寻路算法
当前网址:http://scyanting.com/article/ggcsdj.html