Java实现Dijkstra输出最短路径的实例
Java实现Dijkstra输出指定起点到终点的最短路径
前言：
最近在公司参加了一个比赛，其中涉及的一个问题，可以简化成如是描述：一个二维矩阵，每个点都有权重，需要找出从指定起点到终点的最短路径。
马上就想到了Dijkstra算法，所以又重新温故了一遍，这里给出Java的实现。
而输出最短路径的时候，在网上也进行了查阅，没发现什么标准的方法，于是在下面的实现中，我给出了一种能够想到的比较精简的方式：利用prev[]数组进行递归输出。
packagegraph.dijsktra;
importgraph.model.Point;
importjava.util.*;
/**
*CreatedbyMHXon2017/9/13.
*/
publicclassDijkstra{
privateint[][]map;//地图结构保存
privateint[][]edges;//邻接矩阵
privateint[]prev;//前驱节点标号
privateboolean[]s;//S集合中存放到起点已经算出最短路径的点
privateint[]dist;//dist[i]表示起点到第i个节点的最短路径
privateintpointNum;//点的个数
privateMapindexPointMap;//标号和点的对应关系
privateMappointIndexMap;//点和标号的对应关系
privateintv0;//起点标号
privatePointstartPoint;//起点
privatePointendPoint;//终点
privateMappointPointMap;//保存点和权重的映射关系
privateListallPoints;//保存所有点
privateintmaxX;//x坐标的最大值
privateintmaxY;//y坐标的最大值
publicDijkstra(intmap[][],PointstartPoint,PointendPoint){
this.maxX=map.length;
this.maxY=map[0].length;
this.pointNum=maxX*maxY;
this.map=map;
this.startPoint=startPoint;
this.endPoint=endPoint;
init();
dijkstra();
}
/**
*打印指定起点到终点的最短路径
*/
publicvoidprintShortestPath(){
printDijkstra(pointIndexMap.get(endPoint));
}
/**
*初始化dijkstra
*/
privatevoidinit(){
//初始化所有变量
edges=newint[pointNum][pointNum];
prev=newint[pointNum];
s=newboolean[pointNum];
dist=newint[pointNum];
indexPointMap=newHashMap<>();
pointIndexMap=newHashMap<>();
pointPointMap=newHashMap<>();
allPoints=newArrayList<>();
//将map二维数组中的所有点转换成自己的结构
intcount=0;
for(intx=0;xgetAroundPoints(Pointpoint){
ListaroundPoints=newArrayList<>();
intx=point.getX();
inty=point.getY();
aroundPoints.add(pointPointMap.get(newPoint(x-1,y)));
aroundPoints.add(pointPointMap.get(newPoint(x,y+1)));
aroundPoints.add(pointPointMap.get(newPoint(x+1,y)));
aroundPoints.add(pointPointMap.get(newPoint(x,y-1)));
aroundPoints.removeAll(Collections.singleton(null));//剔除不在地图范围内的null点
returnaroundPoints;
}
publicstaticvoidmain(String[]args){
intmap[][]={
{1,2,2,2,2,2,2},
{1,0,2,2,0,2,2},
{1,2,0,2,0,2,2},
{1,2,2,0,2,0,2},
{1,2,2,2,2,2,2},
{1,1,1,1,1,1,1}
};//每个点都代表权重，没有方向限制
PointstartPoint=newPoint(0,3);//起点
PointendPoint=newPoint(5,6);//终点
Dijkstradijkstra=newDijkstra(map,startPoint,endPoint);
dijkstra.printShortestPath();
}
}
packagegraph.model;
publicclassPoint{
privateintx;
privateinty;
privateintvalue;
publicPoint(intx,inty){
this.x=x;
this.y=y;
}
publicPoint(intx,inty,intvalue){
this.x=x;
this.y=y;
this.value=value;
}
publicintgetX(){
returnx;
}
publicvoidsetX(intx){
this.x=x;
}
publicintgetY(){
returny;
}
publicvoidsetY(inty){
this.y=y;
}
publicintgetValue(){
returnvalue;
}
publicvoidsetValue(intvalue){
this.value=value;
}
@Override
publicStringtoString(){
return"{"+
"x="+x+
",y="+y+
'}';
}
@Override
publicbooleanequals(Objecto){
if(this==o)returntrue;
if(o==null||getClass()!=o.getClass())returnfalse;
Pointpoint=(Point)o;
if(x!=point.x)returnfalse;
returny==point.y;
}
@Override
publicinthashCode(){
intresult=x;
result=31*result+y;
returnresult;
}
}
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望通过本文能帮助到大家，谢谢大家对本站的支持！