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 <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集合里面目前更新的距离离起始点最短路径的节点。基于广度优先原则，可以避免路径权重不均导致错寻的情况。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持CodeAE代码之家。
原文链接：https://blog.csdn.net/jake_gogo/article/details/38175137
http://www.zzvips.com/article/175494.html
页:
[1]