The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!
- 路线是单向的，比如有A->B的路线，并不表示有B->A的路线；即使同时存在A->B和B->A的路线，两条路线的距离也可能不同；
- 计算给定的三个问题
- 给定路线的距离
- 两个站点间的不同路线
- 两个站点间的最短路线
- 输入
- 给定路线是有方向的，后面的数字表示两站点间的距离；
- 路线不会出现多次；
- 终点和起点不会相同；
- 输出：
- 1-5，如果路线不存在，输出“NO SUCH ROUTE”，否则输出路线距离；
- 6，输出从C站点起始，结束也在C站点，最大经过3个站点的路线数（给定数据的结果：C-D-C，C-E-B-C）；
- 7，从站点A起始，结束与C站点，经过4个站点的路线数（给定数据的结果：A-B-C-D-C, A-D-C-D-C, A-D-E-B-C）；
- 8，从A站点到C站点的最短路线距离；
- 9，从B站点到B站点的最短路线距离；
- 10，从C站点到C站点，总距离小于30的不同路线（给定数据的结果：C-D-C, C-E-B-C, C-E-B-C-D-C, C-D-C-E-B-C, C-D-E-B-C, C-E-B-C-E-B-C, C-E-B-C-E-B-C-E-B-C）；
包结构
- com.tw.trains
- Main.java 程序运行入口，负责构建测试数据，已经调用api；
- Maps.java 程序路主要功能提供类；
- Route.java 路线实体类信息；
- Town.java 车站实体类信息；
- com.tw.trans.data
- TownsEnum.java 程序测试路线初始化
- com.tw.trans.exception
- TransException 程序自定义异常，再需要的情况下抛出，程序捕获做适当的处理
项目源码地址：https://github.com/elfdemonster/Trains
主要实现类Maps
-
该类中维护两个map
- directTownsMaps 直连的站点路线
- routeMaps 已经构建好的路线（完备的考虑应该路线构持久化或者缓存）
-
map初始化
public static void init() { //Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 if(null == Maps.directTownsMaps) { Maps.directTownsMaps = new HashMap<Town, Map<String, Route>>(); } if(null == Maps.routeMaps) { Maps.routeMaps = new HashMap<Town, Map<String, Route>>(); } TownsEnum[] initData = TownsEnum.values(); for(TownsEnum te : initData) { if (Maps.directTownsMaps.containsKey(te.getStart())) { Maps.directTownsMaps.get(te.getStart()).put( te.getEnd().getName(), new Route(te.getStart(), te.getEnd(), te.getRoutes(), te.getDistance())); } else { Map<String, Route> diretTowns = new HashMap<String, Route>(); diretTowns.put(te.getEnd().getName(), new Route(te.getStart(), te.getEnd(), te.getRoutes(), te.getDistance())); Maps.directTownsMaps.put(te.getStart(), diretTowns); } } //System.out.println("Maps.directTownsMaps init success! " + Maps.directTownsMaps); } -
给定路线计算距离
public static int getDistance(Route route) throws TrainsException { if(null == route) { return 0; } Town startTown = route.getStartTown(); // 如果已缓存路线，可以直接取出结果 if (null != Maps.routeMaps && Maps.routeMaps.containsKey(startTown) && Maps.routeMaps.get(startTown).containsKey(route.getRoutes())) { return Maps.routeMaps.get(startTown).get(route.getRoutes()) .getDistance(); } int distance = 0; if(null != Maps.directTownsMaps.get(startTown)) { String[] allTowns = route.getRoutes().split("-"); if (allTowns.length == 2) { if (null == Maps.directTownsMaps.get(startTown).get( route.getEndTown().getName())) { throw new TrainsException(Maps.NO_SUCH_ROUTE); } distance += Maps.directTownsMaps.get(startTown) .get(route.getEndTown().getName()).getDistance(); } else { if (null == Maps.directTownsMaps.get(startTown).get(allTowns[1])) { throw new TrainsException(Maps.NO_SUCH_ROUTE); } else { Route tmp = new Route(new Town(allTowns[1], allTowns[1]), new Town(allTowns[2], allTowns[2]), route .getRoutes().substring(2)); distance += Maps.directTownsMaps.get(startTown).get(allTowns[1]) .getDistance() + Maps.getDistance(tmp); } } // 将算好的路线缓存起来 cacheRoute(route, startTown, distance); return distance; } throw new TrainsException(Maps.NO_SUCH_ROUTE); } -
根据给定起始站，以及允许最大站数，计算有多少种路线
/** * 根据给定起始站，以及允许最大站数，计算有多少种路线 * @param route 带有起始站信息的路线 * @param countTowns 跨站数 * @param max true：指定数最大跨站数 false：指定数为确定站数 * @return */ public static int getRoutesCount(Route route, int countTowns, boolean max) { if(null == route || 0 == countTowns) { return 0; } Map<String, Route> routes = Maps.getRoutes(route, countTowns, max, false, 0); if(max) { return null == routes ? 0 : routes.size(); } else { if(null != routes && !routes.isEmpty()) { //System.out.println(routes); Map<String, Route> result = new HashMap<String, Route>(); Set<String> keys = routes.keySet(); Iterator<String> it = keys.iterator(); while(it.hasNext()) { String key = it.next(); if(key.split(Maps.ROUTE_JOINER).length == countTowns) { result.put(key, routes.get(key)); } } //System.out.println(result); return result.size(); } } return 0; } -
获取两站之间的最短距离
/**
* 获取两站之间的最短距离
* @param route
* @return
*/
public static int getShortestDistance(Route route)
{
Map<String, Route> routes = Maps.getRoutes(route, 100, false, true, 0);
if (null != routes && !routes.isEmpty()) {
//System.out.println(routes);
List<Route> values = new ArrayList<Route>(routes.values());
Route result = values.get(0);
for(int i=1; i<values.size(); i++)
{
if(values.get(i).getDistance() < result.getDistance())
{
result = values.get(i);
}
}
//System.out.println(result);
return result.getDistance();
}
return 0;
}
-
获取最大指定距离下的路线数
/** * 获取最大指定距离下的路线数 * @param route * @param maxDistance * @return */ public static int getMaxDistanceRoutesCount(Route route, int maxDistance) { Map<String, Route> result = Maps.getRoutes(route, 0, false, false, maxDistance); return null == result ? 0 : result.size(); } -
获取最大指定距离下的路线
/** * 获取最大指定距离下的路线 * @param route * @param maxDistance * @return */ public static Map<String, Route> getMaxDistanceRoutes(Route route, int maxDistance) { return Maps.getRoutes(route, 0, false, false, maxDistance); } -
查找路线
/** * 查找路线 * @param route 带有起始站信息的路线 * @param countTowns 跨站数 * @param max 跨站数是否是最大站数 true：指定数最大跨站数 false：指定数为确定站数 * @param shortest 是否寻找最短路线 true：最短路线 * @param maxDistance 最大距离 * @return */ public static Map<String, Route> getRoutes(Route route, int countTowns, boolean max, boolean shortest, int maxDistance) { Town startTown = route.getStartTown(); Town endTown = route.getEndTown(); Map<String, Route> directTownsMap = Maps.directTownsMaps.get(startTown); Map<String, Route> result = new HashMap<String, Route>(); StringBuffer sb = new StringBuffer(startTown.getName()); sb.append("-"); Set<String> keys = directTownsMap.keySet(); Iterator<String> it = keys.iterator(); // 无论是否最短路径都给定次数，防止起始站相互通，造成死循环 while(it.hasNext() && (countTowns>0 || (countTowns > -1 && shortest) || maxDistance>0) ) { String key = (String) it.next(); if(key.equals(endTown.getName())) { sb.append(key); route.setRoutes(sb.toString()); route.setDistance(Maps.directTownsMaps.get(startTown).get(key) .getDistance() + route.getDistance()); route.setCountTowns(2); result.put(sb.toString(), route); // 最短路径 出现则停止 if(shortest) { break; } if(maxDistance > 0 && route.getDistance()>maxDistance) { result.remove(sb.toString()); break; } // 不是指定最大站则允许继续往下找 if(!max) { Route tmp = new Route(route.getStartTown(), route.getEndTown(), route.getRoutes(), route.getDistance() - Maps.directTownsMaps.get(startTown) .get(key).getDistance()); innerIterator(tmp, countTowns, max, shortest, maxDistance, startTown, endTown, directTownsMap, result, sb, key); } }else { innerIterator(route, countTowns, max, shortest, maxDistance, startTown, endTown, directTownsMap, result, sb, key); } } return result; } -
关键的迭代方法
private static void innerIterator(Route route, int countTowns, boolean max, boolean shortest, int maxDistance, Town startTown, Town endTown, Map<String, Route> directTownsMap, Map<String, Route> result, StringBuffer sb, String key) { Route tmp = new Route(directTownsMap.get(key).getEndTown(), endTown); tmp.setDistance(route.getDistance() + Maps.directTownsMaps.get(startTown).get(key).getDistance()); Map<String, Route> tmpResult = Maps.getRoutes(tmp, countTowns - 1, max, shortest, maxDistance); Set<String> keystmp = tmpResult.keySet(); Iterator<String> ittmp = keystmp.iterator(); while(ittmp.hasNext()) { String keytpm = ittmp.next(); Route routetmp = new Route(startTown, tmpResult.get(keytpm).getEndTown()); routetmp.setRoutes(startTown.getName() + "-" + keytpm); routetmp.setCountTowns(tmpResult.get(keytpm).getCountTowns() + 1); routetmp.setDistance(tmpResult.get(keytpm).getDistance()); result.put(routetmp.getRoutes(), routetmp); if(maxDistance > 0 && routetmp.getDistance()>maxDistance) { result.remove(sb.toString()); continue; } } } -
缓存路线
private static void cacheRoute(Route route, Town startTown, int distance) { if (null != Maps.routeMaps) { route.setDistance(distance); if (Maps.routeMaps.containsKey(startTown)) { Maps.routeMaps.get(startTown).put(route.getRoutes(), route); } else { Map<String, Route> tmp = new HashMap<String, Route>(); tmp.put(route.getRoutes(), route); Maps.routeMaps.put(startTown, tmp); } } }
网友评论