java实现地图最短路径问题

《java实现地图最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编辑：civvy第4页2021-10-1用JAVA实现地图最短路径问题如图，是一个简单的模拟城市路线地图，那么如何编写程序实现：给出任意两个城市，算出用时最短的路线呢？京沪圳汉渝乌261071853注：图中黑点代表城市，数字代表往返两城市间所需的时间JAVA实现代码如下：publicclassMyMap{/*---城市路线对象---*/publicclassWay{Stringfrom;Stringto;intcost;}Mapmap=newHashMap();//储存所有城市路线ListreachedWay=newArrayList();//储存到

2、达目的地所经过的城市MaprouteMap=newHashMap();//储存到达目的地所经过的城市和所用的时间，key为时间，value为reachedWay//intshortestTime=0;//储存最短时间，用于只输出最短路径的情况/*---添加路线，双向添加---*/publicvoidaddRoute(Stringcity1,Stringcity2,intcost){ListcityList1=(List)map.get(city1);//城市1路线集合if(cityList1==null){cityList1=newArrayList

3、();map.put(city1,cityList1);}编辑：civvy第4页2021-10-1Wayway1=newWay();way1.from=city1;way1.to=city2;way1.cost=cost;/*---不存在该路线，则添加---*/if(!cityList1.contains(way1)){cityList1.add(way1);}ListcityList2=(List)map.get(city2);//城市2路线集合if(cityList2==null){cityList2=newArrayList();map.put

4、(city2,cityList2);}Wayway2=newWay();way2.from=city2;way2.to=city1;way2.cost=cost;/*---不存在该路线，则添加---*/if(!cityList2.contains(way2)){cityList2.add(way2);}}/*---计算最短路径、最短时间---*/publicvoidrun(Stringfrom,Stringto){inttempTime=0;//储存所花时间的临时变量if(reachedWay.contains(from)){//走过的不走retur

5、n;}reachedWay.add(from);//把经过的城市加入到城市集合中if(reachedWay.size()>1){/*---计算所花时间---*/ListinitList=(List)map.get(reachedWay.get(0));for(intj=0;j

6、(shortestTime!=0&&tempTime>shortestTime){编辑：civvy第4页2021-10-1//return;//}}}for(inti=1;i

7、t(i+1))){tempTime+=w.cost;/*---用于不需要循环输出所有路线，只输出最短路径，效率很高---*///if(shortestTime!=0&&tempTime>shortestTime){//return;//}}}}}}/*---到达---*/if(from.equals(to)){//shortestTime=tempTime;Stringroute=reachedWay.get(0).toString();for(inti=1;i"+reachedWa

8、y.get(i).toString();}System.out.println(route+"t用时："+