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 <T> 节点主键
 */
public class Maps<T> {

 /**
 * 所有的节点集合
 * 节点Id - 节点
 */
 private Map<T, Node<T>> nodes = new HashMap<T, Node<T>>();

 /**
 * 地图构建器
 *
 * @author jake
 * @date 2014-7-26-下午9:47:44
 */
 public static class MapBuilder<T> {

 /**
  * map实例
  */
 private Maps<T> map = new Maps<T>();

 /**
  * 构造MapBuilder
  *
  * @return MapBuilder
  */
 public MapBuilder<T> create() {
  return new MapBuilder<T>();
 }

 /**
  * 添加节点
  *
  * @param node 节点
  * @return
  */
 public MapBuilder<T> addNode(Node<T> node) {
  map.nodes.put(node.getId(), node);
  return this;
 }

 /**
  * 添加路线
  *
  * @param node1Id 节点Id
  * @param node2Id 节点Id
  * @param weight 权重
  * @return
  */
 public MapBuilder<T> addPath(T node1Id, T node2Id, int weight) {
  Node<T> node1 = map.nodes.get(node1Id);
  if (node1 == null) {
  throw new RuntimeException("无法找到节点:" + node1Id);
  }

  Node<T> 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<T> build() {
  return this.map;
 }

 }

 /**
 * 节点
 *
 * @author jake
 * @date 2014-7-26-下午9:51:31
 * @param <T> 节点主键类型
 */
 public static class Node<T> {

 /**
  * 节点主键
  */
 private T id;

 /**
  * 节点联通路径
  * 相连节点 - 权重
  */
 private Map<Node<T>, Integer> childs = new HashMap<Node<T>, Integer>();

 /**
  * 构造方法
  * @param id 节点主键
  */
 public Node(T id) {
  this.id = id;
 }

 /**
  * 获取实例
  * @param id 主键
  * @return
  */
 public static <T> Node<T> valueOf(T id) {
  return new Node<T>(id);
 }

 /**
  * 是否有效
  * 用于动态变化节点的可用性
  * @return
  */
 public boolean validate() {
  return true;
 }

 public T getId() {
  return id;
 }

 public void setId(T id) {
  this.id = id;
 }

 public Map<Node<T>, Integer> getChilds() {
  return childs;
 }

 protected void setChilds(Map<Node<T>, Integer> childs) {
  this.childs = childs;
 }

 @Override
 public String toString() {
  StringBuilder sb = new StringBuilder();
  sb.append(this.id).append("[");
  for (Iterator<Entry<Node<T>, Integer>> it = childs.entrySet().iterator(); it.hasNext();) {
  Entry<Node<T>, 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<T, Node<T>> 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)图最短路径搜索算法
 * <br/>每次开始新的搜索需要创建此类对象
 * @param <T> 节点的主键类型
 * @author jake
 * @date 2014-7-26-下午9:45:07
 */
public class MapSearcher<T> {

 /**
 * 最短路径搜索结果类
 * @author jake
 * @date 2014-7-27-下午3:55:11
 * @param <T> 节点的主键类型
 */
 public static class SearchResult<T> {
 /**
  * 最短路径结果
  */
 List<T> path;
 /**
  * 最短距离
  */
 Integer distance;

 /**
  * 获取实例
  * @param path 最短路径结果
  * @param distance 最短路径距离
  * @return
  */
 protected static <T> SearchResult<T> valueOf(List<T> path, Integer distance) {
  SearchResult<T> r = new SearchResult<T>();
  r.path = path;
  r.distance = distance;
  return r;
 }

 public List<T> getPath() {
  return path;
 }
 public Integer getDistance() {
  return distance;
 }

 @Override
 public String toString() {
  StringBuffer sb = new StringBuffer();
  sb.append("path:");
  for(Iterator<T> 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<T> map;
 /**
 * 开始节点
 */
 Maps.Node<T> startNode;
 /**
 * 结束节点
 */
 Maps.Node<T> targetNode;
 /**
 * 开放的节点
 */
 Set<Maps.Node<T>> open = new HashSet<Maps.Node<T>>();
 /**
 * 关闭的节点
 */
 Set<Maps.Node<T>> close = new HashSet<Maps.Node<T>>();
 /**
 * 最短路径距离
 */
 Map<Maps.Node<T>, Integer> path = new HashMap<Maps.Node<T>, Integer>();
 /**
 * 最短路径
 */
 Map<T, List<T>> pathInfo = new HashMap<T, List<T>>();

 /**
 * 初始化起始点
 * <br/>初始时，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<T> init(T source, Maps<T> map, Set<T> closeSet) {

 Map<T, Maps.Node<T>> nodeMap = map.getNodes();
 Maps.Node<T> startNode = nodeMap.get(source);
 //将初始节点放到close
 close.add(startNode);
 //将其他节点放到open
 for(Maps.Node<T> node : nodeMap.values()) {
  if(!closeSet.contains(node.getId()) && !node.getId().equals(source)) {
  this.open.add(node);
  }
 }

 // 初始路径
 T startNodeId = startNode.getId();
 for(Entry<Maps.Node<T>, Integer> entry : startNode.getChilds().entrySet()) {
  Maps.Node<T> node = entry.getKey();
  if(open.contains(node)) {
  T nodeId = node.getId();
  path.put(node, entry.getValue());
  pathInfo.put(nodeId, new ArrayList<T>(Arrays.asList(startNodeId, nodeId)));
  }
 }

 for(Maps.Node<T> node : nodeMap.values()) {
  if(open.contains(node) && !path.containsKey(node)) {
  path.put(node, Integer.MAX_VALUE);
  pathInfo.put(node.getId(), new ArrayList<T>(Arrays.asList(startNodeId)));
  }
 }
 this.startNode = startNode;
 this.map = map;
 return startNode;
 }

 /**
 * 递归Dijkstra
 * @param start 已经选取的最近节点
 */
 protected void computePath(Maps.Node<T> start) {
 // 从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
 Maps.Node<T> 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<Maps.Node<T>, Integer> childs = nearest.getChilds();
 for (Maps.Node<T> 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<T> path = new ArrayList<T>(pathInfo.get(nearest.getId()));
   path.add(child.getId());
   pathInfo.put(child.getId(), path);
  }
  }
 }
// computePath(start);// 重复执行自己,确保所有子节点被遍历
 computePath(nearest);// 向外一层层递归,直至所有顶点被遍历
 }

 /**
 * 获取与node最近的子节点
 */
 private Maps.Node<T> getShortestPath(Maps.Node<T> node) {
 Maps.Node<T> res = null;
 int minDis = Integer.MAX_VALUE;
 for (Maps.Node<T> 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<T> getResult(T target) {
 Maps.Node<T> 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<Map.Entry<T, List<T>>> pathInfos = pathInfo.entrySet();
 for (Map.Entry<T, List<T>> pathInfo : pathInfos) {
  System.out.println(pathInfo.getKey() + ":" + pathInfo.getValue());
 }
 }

 /**
 * 测试方法
 */
 @org.junit.Test
 public void test() {

 MapBuilder<String> mapBuilder = new Maps.MapBuilder<String>().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<String> map = mapBuilder.build();

 //创建路径搜索器(每次搜索都需要创建新的MapSearcher)
 MapSearcher<String> searcher = new MapSearcher<String>();
 //创建关闭节点集合
 Set<String> closeNodeIdsSet = new HashSet<String>();
 closeNodeIdsSet.add("C");
 //设置初始节点
 searcher.init("A", map, closeNodeIdsSet);
 //获取结果
 SearchResult<String> result = searcher.getResult("G");
 System.out.println(result);
 //test.printPathInfo();
 }

}

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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。