JAVA学习：JAVA实现地图最短路径问题

用JAVA实现地图最短路径问题

如图，是一个简单的模拟城市路线地图，那么如何编写程序实现：给出任意两个城市，算出用时最短的路线呢？

注：图中黑点代表城市，数字代表往返两城市间所需的时间

JAVA实现代码如下：

public class MyMap {

/* ---添加路线，双向添加--- */ // int shortestTime=0; //储存最短时间，用于只输出最短路径的情况 Map map = new HashMap();// 储存所有城市路线 List reachedWay = new ArrayList();// 储存到达目的地所经过的城市 Map routeMap = new HashMap();// 储存到达目的地所经过的城市和所用的时间，/* ---城市路线对象--- */ public class Way { } String from; String to; int cost; key为时间，value为reachedWay

} Way way1 = new Way(); way1.from = city1; way1.to = city2; way1.cost = cost; List cityList1 = (List) map.get(city1);// 城市1路线集合 if (cityList1 == null) { } cityList1 = new ArrayList(); map.put(city1, cityList1); /* ---不存在该路线，

则添加--- */ if (!cityList1.contains(way1)) { } List cityList2 = (List) map.get(city2);// 城市2路线集合 if (cityList2 == null) { } Way way2 = new Way(); way2.from = city2; way2.to = city1; way2.cost = cost; /* ---不存在该路线，则添加--- */ if (!cityList2.contains(way2)) { } cityList2.add(way2); cityList2 = new ArrayList(); map.put(city2, cityList2); cityList1.add(way1); /*

3---计算最短路径、最短时间---*/ public void run(String from, String to) { int tempTime = 0;// 储存所花时间的临时变量 if (reachedWay.contains(from)) {// 走过的不走 } reachedWay.add(from);// 把经过的城市加入到城市集合中 if (reachedWay.size() > 1) { /* ---计算所花时间--- */ List initList = (List) map.get(reachedWay.get(0)); return;

if (from.equals(to)) { /*---到达---*/ } } Way w = (Way) initList.get(j); if (w.to.equals(reachedWay.get(1))) { tempTime += w.cost; /* ---用于不需要循环输出所有路线，只输出最短路径，效率很高--- */ } for (int i = 1; i < reachedWay.size(); i++) { // 所经过的城市用时加起来 List toList = (List) map.get(reachedWay.get(i)); for (int j = 0; j < toList.size(); j++) { Way w = (Way) toList.get(j); if (i + 1 < reachedWay.size()) { if (w.to.equals(reachedWay.get(i + 1))) { tempTime += w.cost; } // if(shortestTime!=0&&tempTime>shortestTime){ // return; // } /*

---用于不需要循环输出所有路线，只输出最短路径，效率很高--- */ // if(shortestTime!=0&&tempTime>shortestTime){ // return; // } } } } // shortestTime=tempTime; String route = reachedWay.get(0).toString(); for (int i = 1; i < reachedWay.size(); i++) { } System.out.println(route + "\t用时：" + tempTime); routeMap.put(tempTime, route); tempTime = 0; reachedWay.remove(reachedWay.size() - 1);// 到达后退回去，走下route += "->" + reachedWay.get(i).toString(); 一路线

/*---输出用时最短的路线---*/ /*---没到达---*/ } // 获得from城市能够到达到城市列表 List routeList = (List) map.get(from); for (Iterator iterator = routeList.iterator(); }

Way way = (Way) iterator.next(); run(way.to, to); iterator.hasNext();) { reachedWay.remove(reachedWay.size() - 1);// 走完退回去，走下一路线 } public void show(String city1, String city2) { run(city1, city2); Set s = routeMap.keySet(); Object[] a = s.toArray(); int shortestTime = (Integer) a[0]; for (int i = 0; i < a.length; i++) { } System.out.println("\n最短路径为：\n" + routeMap.get(shortestTime)

+ shortestTime); if ((Integer) a[i] < shortestTime) { } shortestTime = (Integer) a[i]; + "\t用时："

} public static void main(String[] args) { MyMap map = new MyMap(); 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("汉", "京");

学习有困难可以加扣：578024144进行交流得到帮助还可以关注微信公众号：javaniuniu获取免费得听课权限