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

2023-08-31 16:28:04 194

【引用】迪杰斯特拉(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另外一篇博客的算法，我对此做了一些改进。

构建地图:

importjava.util.HashMap;
importjava.util.Iterator;
importjava.util.Map;
importjava.util.Map.Entry;

/**
*地图
*@authorjake
*@date2014-7-26-下午10:40:10
*@param节点主键
*/
publicclassMaps{

/**
*所有的节点集合
*节点Id-节点
*/
privateMap>nodes=newHashMap>();

/**
*地图构建器
*
*@authorjake
*@date2014-7-26-下午9:47:44
*/
publicstaticclassMapBuilder{

/**
*map实例
*/
privateMapsmap=newMaps();

/**
*构造MapBuilder
*
*@returnMapBuilder
*/
publicMapBuildercreate(){
returnnewMapBuilder();
}

/**
*添加节点
*
*@paramnode节点
*@return
*/
publicMapBuilderaddNode(Nodenode){
map.nodes.put(node.getId(),node);
returnthis;
}

/**
*添加路线
*
*@paramnode1Id节点Id
*@paramnode2Id节点Id
*@paramweight权重
*@return
*/
publicMapBuilderaddPath(Tnode1Id,Tnode2Id,intweight){
Nodenode1=map.nodes.get(node1Id);
if(node1==null){
thrownewRuntimeException("无法找到节点:"+node1Id);
}

Nodenode2=map.nodes.get(node2Id);
if(node2==null){
thrownewRuntimeException("无法找到节点:"+node2Id);
}

node1.getChilds().put(node2,weight);
node2.getChilds().put(node1,weight);
returnthis;
}

/**
*构建map
*@returnmap
*/
publicMapsbuild(){
returnthis.map;
}

}

/**
*节点
*
*@authorjake
*@date2014-7-26-下午9:51:31
*@param节点主键类型
*/
publicstaticclassNode{

/**
*节点主键
*/
privateTid;

/**
*节点联通路径
*相连节点-权重
*/
privateMap,Integer>childs=newHashMap,Integer>();

/**
*构造方法
*@paramid节点主键
*/
publicNode(Tid){
this.id=id;
}

/**
*获取实例
*@paramid主键
*@return
*/
publicstaticNodevalueOf(Tid){
returnnewNode(id);
}

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


publicTgetId(){
returnid;
}

publicvoidsetId(Tid){
this.id=id;
}

publicMap,Integer>getChilds(){
returnchilds;
}

protectedvoidsetChilds(Map,Integer>childs){
this.childs=childs;
}

@Override
publicStringtoString(){
StringBuildersb=newStringBuilder();
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("]");
returnsb.toString();
}

}

/**
*获取地图的无向图节点
*@return节点Id-节点
*/
publicMap>getNodes(){
returnnodes;
}

}

开始寻路:

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.HashMap;
importjava.util.HashSet;
importjava.util.Iterator;
importjava.util.List;
importjava.util.Map;
importjava.util.Map.Entry;
importjava.util.Set;

importcom.my9yu.sanguohun2.utils.dijkstra.Maps.MapBuilder;

/**
*迪杰斯特拉(Dijkstra)图最短路径搜索算法
*
每次开始新的搜索需要创建此类对象
*@param节点的主键类型
*@authorjake
*@date2014-7-26-下午9:45:07
*/
publicclassMapSearcher{

/**
*最短路径搜索结果类
*@authorjake
*@date2014-7-27-下午3:55:11
*@param节点的主键类型
*/
publicstaticclassSearchResult{
/**
*最短路径结果
*/
Listpath;
/**
*最短距离
*/
Integerdistance;

/**
*获取实例
*@parampath最短路径结果
*@paramdistance最短路径距离
*@return
*/
protectedstaticSearchResultvalueOf(Listpath,Integerdistance){
SearchResultr=newSearchResult();
r.path=path;
r.distance=distance;
returnr;
}

publicListgetPath(){
returnpath;
}
publicIntegergetDistance(){
returndistance;
}

@Override
publicStringtoString(){
StringBuffersb=newStringBuffer();
sb.append("path:");
for(Iteratorit=this.path.iterator();it.hasNext();){
sb.append(it.next());
if(it.hasNext()){
sb.append("->");
}
}
sb.append("\n").append("distance:").append(distance);
returnsb.toString();
}

}

/**
*地图对象
*/
Mapsmap;
/**
*开始节点
*/
Maps.NodestartNode;
/**
*结束节点
*/
Maps.NodetargetNode;
/**
*开放的节点
*/
Set>open=newHashSet>();
/**
*关闭的节点
*/
Set>close=newHashSet>();
/**
*最短路径距离
*/
Map,Integer>path=newHashMap,Integer>();
/**
*最短路径
*/
Map>pathInfo=newHashMap>();

/**
*初始化起始点
*
初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为"起点s到该顶点的距离"
*[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。
*@paramsource起始节点的Id
*@parammap全局地图
*@paramcloseSet已经关闭的节点列表
*@return
*/
@SuppressWarnings("unchecked")
publicMaps.Nodeinit(Tsource,Mapsmap,SetcloseSet){

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

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

for(Maps.Nodenode:nodeMap.values()){
if(open.contains(node)&&!path.containsKey(node)){
path.put(node,Integer.MAX_VALUE);
pathInfo.put(node.getId(),newArrayList(Arrays.asList(startNodeId)));
}
}
this.startNode=startNode;
this.map=map;
returnstartNode;
}


/**
*递归Dijkstra
*@paramstart已经选取的最近节点
*/
protectedvoidcomputePath(Maps.Nodestart){
//从U中选出"距离最短的顶点k"，并将顶点k加入到S中；同时，从U中移除顶点k。
Maps.Nodenearest=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.Nodechild:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
IntegernewCompute=path.get(nearest)+childs.get(child);
if(path.get(child)>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child,newCompute);

Listpath=newArrayList(pathInfo.get(nearest.getId()));
path.add(child.getId());
pathInfo.put(child.getId(),path);
}
}
}
//computePath(start);//重复执行自己,确保所有子节点被遍历
computePath(nearest);//向外一层层递归,直至所有顶点被遍历
}

/**
*获取与node最近的子节点
*/
privateMaps.NodegetShortestPath(Maps.Nodenode){
Maps.Noderes=null;
intminDis=Integer.MAX_VALUE;
for(Maps.Nodeentry:path.keySet()){
if(open.contains(entry)){
intdistance=path.get(entry);
if(distancegetResult(Ttarget){
Maps.NodetargetNode=this.map.getNodes().get(target);
if(targetNode==null){
thrownewRuntimeException("目标节点不存在!");
}
this.targetNode=targetNode;
//开始计算
this.computePath(startNode);
returnSearchResult.valueOf(pathInfo.get(target),path.get(targetNode));
}

/**
*打印出所有点的最短路径
*/
publicvoidprintPathInfo(){
Set>>pathInfos=pathInfo.entrySet();
for(Map.Entry>pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue());
}
}


/**
*测试方法
*/
@org.junit.Test
publicvoidtest(){

MapBuildermapBuilder=newMaps.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
Mapsmap=mapBuilder.build();

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

}

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

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

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

热门推荐

随机推荐