【引用】迪杰斯特拉(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另外一篇博客的算法，我对此做了一些改进。http://blog.csdn.net/javaman_chen/article/details/8254309
构建地图:
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集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则，可以避免路径权重不均导致错寻的情况。
相关推荐
"java实现dijkstra最短路径寻路算法" Dijkstra算法是典型的最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），直到扩展到终点为止。下面是Java...
【标题】"模拟最短路径寻路（JAVA界面）"所涉及的知识点主要集中在图论、算法和Java编程上。图论是计算机科学中的一个重要分支，用于表示和解决各种网络结构的问题，如交通网络、通信网络等。在这个项目中，核心任务...
描述中提到的"cal文件夹是计算类"可能包含了自定义的算法实现，这些算法可能基于Dijkstra算法、A*算法或者其他图搜索策略来寻找两个点之间的最短路径。Dijkstra算法是一种广泛应用的单源最短路径算法，适用于所有边...
而“N最短路径算法”则是在图论和网络分析中广泛应用的一种算法，常用于解决多目标寻路问题。 中文分词是将连续的汉字序列切分成具有语义的独立单位，如单词或词组的过程。由于中文没有明显的空格分隔，因此中文...
1. **迪杰斯特拉算法 (Dijkstra's Algorithm)**：这是一种用于找到单源最短路径的算法。它从一个起点开始，逐步扩展最短路径到图中的所有其他节点，确保每次选择的都是当前未访问节点中距离起点最近的一个。该算法...
Dijkstra算法是一种单源最短路径算法，适用于有权重的图。它的基本思想是使用优先队列（如二叉堆）存储待访问的节点，并始终选择当前剩余路径最短的节点进行扩展。在每次扩展时，更新其相邻节点的距离，并将这些节点...
总结来说，"java快速易懂寻路算法"是指在Java中设计和实现的一种简单易懂的寻路算法，它可以快速地找出图中节点之间的路径，包括最短路径，并支持正查和逆查。这种算法的实现涉及到图的表示、路径搜索策略以及可能的...
在Java编程中，实现地图最短路径的问题通常涉及到图论和算法的应用，特别是回溯和递归策略。这里我们讨论的是一种使用递归方法解决此类问题的实例。首先，我们需要理解基本概念： 1. **图**：在本例中，地图被抽象...
A*算法是一种启发式搜索算法，它结合了Dijkstra算法的最短路径保证和优先级队列的效率。它使用一个估价函数f(n) = g(n) + h(n)，其中g(n)是从起点到当前节点的实际代价，h(n)是从当前节点到目标的预估代价。A*算法的...
A*（发音为“A-star”）寻路算法是一种在图形中寻找从起点到终点最短路径的高效算法，尤其适用于游戏开发、地图导航等领域。它结合了Dijkstra算法的全局最优性和启发式搜索的效率，通过引入估计代价来快速找到最佳...
A*寻路算法是计算机图形学、游戏开发和人工智能领域中的一个重要算法，它用于寻找从起点到终点的最短路径。本节将深入探讨A*算法的原理、工作流程及其在Unity引擎中的应用。 A*算法的核心思想是结合了Dijkstra算法...
它结合了Dijkstra算法的最短路径特性与BFS（广度优先搜索）的效率，通过评估函数来指导搜索，以找到从起点到终点的最优路径。在给定的"A*自动寻路算法demo"中，我们可以通过分析提供的Java类来理解其核心实现。 1. ...
Dijkstra算法保证找到最短路径，但计算量较大；A*算法则通过引入启发式函数，提高了寻路效率，适用于实时性要求较高的场景。在Java中实现这些算法，我们需要维护一个优先队列，并不断更新节点的代价和父节点信息。 ...
A星寻路算法(A* Search Algorithm)是一种在图形或网格中寻找从起点到终点最短路径的搜索算法，广泛应用于游戏开发、地图导航、网络路由等领域。它结合了Dijkstra算法的全局最优性和最佳优先搜索的效率，通过引入启发...
A*寻路算法是计算机图形学和游戏开发中常用的一种路径搜索算法，它结合了Dijkstra算法和最佳优先搜索（BFS）的优点，能够在有大量节点的图中找到从起点到终点的最短路径，同时考虑了启发式信息以提高效率。...
它的核心思想是结合了Dijkstra算法的最短路径特性以及优先级队列的效率，同时引入启发式函数来指导搜索方向，以减少探索不必要的节点，从而提高搜索效率。 A*算法的关键组成部分包括以下几个方面： 1. **开放列表...
A星(A*)寻路算法是计算机图形学和游戏开发中常用的一种路径搜索算法，尤其在构建复杂的二维或三维游戏世界时，它能有效地找到两点之间的最短路径。在这个J2ME（Java Micro Edition）版本中，该算法被优化以适应移动...
A*（发音为 "A-star"）算法是一种在图形或网格环境中寻找最短路径的搜索算法，被广泛应用于游戏开发、地图导航、机器人路径规划等领域。在这个特定的场景中，我们讨论的是A*算法的一个J2ME（Java Micro Edition）...
java原始路径寻路算法 关于寻路算法的HappyCoders.eu文章系列的源代码： 英文文章 第1部分： 第2部分： 第3部分： 第4部分： 第5部分： 德国文章 方式1： 等级2： 方式3： 方块4： 标题5：
A星寻路算法(A* Search Algorithm)是一种在图形或网格中寻找从起点到终点最短路径的搜索算法，因其高效性和准确性而广泛应用于游戏开发、地图导航、机器人路径规划等领域。该算法结合了Dijkstra算法的全局最优性与...