北京地铁出行线路规划系统项目总结(Java+Flask+Vue实现)
北京地铁出行线路规划系统项目总结GitHub仓库地址:https://github.com/KeadinZhou/SE-Subway Demo地址:http://10.66.2.161:8080/ (校内网) 项目需求
算法设计项目中最主要的点在于:找出两个站点之间通过最少站数的路线。该点对应的经典模型是“在一个无向图中找出两点之间的最短路径”。各个站点即为无向图中的点,两站间的路径即为无向图中连接两个节点的边,在此需求下,所有边的长度均为 地铁最短路的换乘,最贴近实际的情况是“一次初始化,多次查询”,即在地图确定下来之后可能会有若干次不同点对的查询。而本需求中地铁线路图数据需要与执行程序解耦,每次查询对于地图数据都可能是不同的,所以初始化的时间应该均摊到每次查询中去。由于地铁地图属于稀疏图,且该图中每条边权恒定,故可以直接使用 细节上,为了解决两条线路覆盖的情况下(见下图),连续换乘的问题,需要更好的换乘算法。 解决方法:通过判断站点和前继站点的所在线路是否有重叠来判断是否需要换乘。 存储设计数据存储上,可以采用存点/存边两种形式。在本项目中,存边会明显优于存点。
具体到内容,整个数据文件可以被几条线路分成几个大的模块,每个模块存一条线路的数据,由于地铁站名不存在同名的情况,可以不存线路换乘站点的信息,通过同名同名判断即可。由于同一条边不可能同时属于两条线路,所以在边信息上不会存在冗余。每个模块由一个星号( 样例如下: * 1号线 刘院 西横堤 果酒场 本溪路 ...(省略) 咸水沽北 双桥河 * 9号线 天津站 大王庄 大王庄 十一经路 ...(省略) 架构设计系统整体的计算核心使用 实现细节计算核心数据初始化private static void dataInit(String pathname) { try(FileReader reader = new FileReader(pathname); BufferedReader br = new BufferedReader(reader) ) { String line; String lineName=""; boolean first=false; while((line=br.readLine()) != null) { String[] data = line.split(" "); if(data[0].contains("*")){ lineName=data[1]; first=true; continue; } int id1=getStationId(data[0]); int id2=getStationId(data[1]); if(first){ lineStart.put(lineName,id1); first=false; stations.get(id1).addLines(lineName); } stations.get(id2).addLines(lineName); addEdge(id1,id2,lineName); } Station.count=stationCnt; } catch (Exception e) { e.printStackTrace(); } } 通过约定的数据存储格式进行数据初始化,通过 换乘检测private static String checkSwitchLine(int id1,int id2,int id3){ String linea=edgeLines.get(getEdgeHash(id1,id2)); String lineb=edgeLines.get(getEdgeHash(id2,id3)); if(linea.equals(lineb)) return null; return lineb; } 通过检测相邻两条表是否同属于同一条线路来判断是否需要换乘。 路径查询private static void getShortestPath(String start,String end) throws IOException { int startID=getStationId(start); if(startID>Station.count){ println("错误:没有 " + start + " 这个站"); return; } int endID=getStationId(end); if(endID>Station.count){ println("错误:没有 " + end + " 这个站"); return; } Queue<Integer>q=new LinkedList<>(); q.offer(startID); stations.get(startID).setVis(true); while(!q.isEmpty()){ Station now=stations.get(q.poll()); for(int it:now.getEdges()){ Station tmp=stations.get(it); if(tmp.isVis()) continue; q.offer(it); tmp.setVis(true); tmp.setLastPoint(now.getId()); if(it==endID) break; } } Stack<Integer> path=new Stack<>(); int tip=endID; while(tip!=startID){ path.push(tip); tip=stations.get(tip).getLastPoint(); } ArrayList<Integer> res=new ArrayList<>(); res.add(startID); while(!path.empty()){ int now=path.pop(); res.add(now); } println(res.size()); int tmpa=-1,tmpb=-1; for(int it:res){ if(tmpa!=-1){ String switchMsg=checkSwitchLine(tmpa,tmpb,it); if(switchMsg!=null){ println(switchMsg); } } println(stations.get(it).getName()); tmpa=tmpb; tmpb=it; } } 通过 后端接口后端接口由 全局数据接口@app.route('/data',methods=['GET']) def data(): lines = [] sites = set() file = open('subway.txt','r') for item in file: ll = item.strip().split() if ll[0].find('*') != -1: lines.append(ll[1]) else: sites.add(ll[0]) sites.add(ll[1]) return jsonify({ 'lines': lines,'sites': list(sites) }) 该接口用于查询地铁图中出现的所有线路和所有站点的列表,通过直接读取数据文件实现。 查询接口GET_ALL_CMD = 'java subway -map subway.txt -a %s -o out.txt' GET_PATH_CMD = 'java subway -map subway.txt -b %s %s -o out.txt' @app.route('/query',methods=['POST']) def query(): json_data = request.get_json() all = json_data['isAll'] if all: os.system(GET_ALL_CMD % json_data['query']) else: os.system(GET_PATH_CMD % (json_data['query'][0],json_data['query'][1])) file = open('out.txt','r') res = [] for item in file: res.append(item.strip()) return jsonify({ 'res': res }) 该接口通过前端提交的数据,选择查询线路和查询路径对应的计算核心命令,来使用计算核心来获取线路数据。 前端页面前端页面是用户和程序交互的非常重要的手段。本项目的前端页面使用 运行效果计算核心通过 通过 通过 计算核心的健壮性:不合法命令的检测。 WEB展示前端查询主界面。(路径查询) 当查询时,输入关键字,系统将会自动匹配补全相关的站点供用户选择。 查询的结果。显示每一站的站名,并在需要换乘的站点后面标注换乘的线路。 线路站点查询,可以查询每条线路所包含的所有站点。 线路查询结果。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |