java实现地图最短路径问题.docx
- 文档编号:350482
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:4
- 大小:30.40KB
java实现地图最短路径问题.docx
《java实现地图最短路径问题.docx》由会员分享,可在线阅读,更多相关《java实现地图最短路径问题.docx(4页珍藏版)》请在冰点文库上搜索。
用JAVA实现地图最短路径问题
如图,是一个简单的模拟城市路线地图,那么如何编写程序实现:
给出任意两个城市,算出
用时最短的路线呢?
注:
图中黑点代表城市,数字代表往返两城市间所需的时间
JAVA实现代码如下:
publicclassMyMap{
/*---城市路线对象---*/
publicclassWay{
Stringfrom;
Stringto;
intcost;
}
Mapmap=newHashMap();//储存所有城市路线
ListreachedWay=newArrayList();//储存到达目的地所经过的城市
MaprouteMap=newHashMap();//储存到达目的地所经过的城市和所用的时间,
key为时间,value为reachedWay
//intshortestTime=0;//储存最短时间,用于只输出最短路径的情况
/*---添加路线,双向添加---*/
publicvoidaddRoute(Stringcity1,Stringcity2,intcost){
ListcityList1=(List)map.get(city1);//城市1路线集合
if(cityList1==null){
cityList1=newArrayList();
map.put(city1,cityList1);
}
京
沪
圳
汉
渝
乌
2
1
7
1
5
3
Wayway1=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(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)){//走过的不走
return;
}
reachedWay.add(from);//把经过的城市加入到城市集合中
if(reachedWay.size()>1){
/*---计算所花时间---*/
ListinitList=(List)map.get(reachedWay.get(0));
for(intj=0;j Wayw=(Way)initList.get(j); if(w.to.equals(reachedWay.get (1))){ tempTime+=w.cost; /*---用于不需要循环输出所有路线,只输出最短路径,效率很高---*/ //if(shortestTime! =0&&tempTime>shortestTime){ //return; //} } } for(inti=1;i //所经过的城市用时加起来 ListtoList=(List)map.get(reachedWay.get(i)); for(intj=0;j Wayw=(Way)toList.get(j); if(i+1 if(w.to.equals(reachedWay.get(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 route+="->"+reachedWay.get(i).toString(); } System.out.println(route+"\t用时: "+tempTime); routeMap.put(tempTime,route); tempTime=0; reachedWay.remove(reachedWay.size()-1);//到达后退回去,走下 一路线 return; } /*---没到达---*/ //获得from城市能够到达到城市列表 ListrouteList=(List)map.get(from); for(Iteratoriterator=routeList.iterator(); iterator.hasNext();){ Wayway=(Way)iterator.next(); run(way.to,to); } reachedWay.remove(reachedWay.size()-1);//走完退回去,走下一路线 } /*---输出用时最短的路线---*/ publicvoidshow(Stringcity1,Stringcity2){ run(city1,city2); Sets=routeMap.keySet(); Object[]a=s.toArray(); intshortestTime=(Integer)a[0]; for(inti=0;i if((Integer)a[i] shortestTime=(Integer)a[i]; } } System.out.println("\n最短路径为: \n"+routeMap.get(shortestTime) +"\t用时: " +shortestTime); } publicstaticvoidmain(String[]args){ MyMapmap=newMyMap(); map.addRoute("京","汉",10); map.addRoute("京","沪",4); map.addRoute("京","乌",36); map.addRoute("汉","沪",3); map.addRoute("汉","乌",18); map.addRoute("汉","渝",7); map.addRoute("圳","汉",3); map.addRoute("圳","沪",4); map.addRoute("圳","乌",45); map.addRoute("圳","渝",16); map.show("汉","京"); } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- java 实现 地图 路径 问题