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;//标号和点的对应关系 privateMap pointIndexMap;//点和标号的对应关系 privateintv0;//起点标号 privatePointstartPoint;//起点 privatePointendPoint;//终点 privateMap pointPointMap;//保存点和权重的映射关系 privateList allPoints;//保存所有点 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;x getAroundPoints(Pointpoint){ List aroundPoints=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; } }
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望通过本文能帮助到大家,谢谢大家对本站的支持!