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 sourhttp://ce, 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集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则，可以避免路径权重不均导致错寻的情况。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。