基于图结构实现地铁乘坐线路查询

基于图结构实现地铁乘坐线路查询

github-python算法和flaskapp部分：repo

github-android部分：repo

flaskapp接口文档：传送门

深度了解Dijkstra优化算法：传送门

personblog:github_page or csdnblog

问题描述

编写一个程序实现地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。

1.采用Dijkstra算法实现，使用优先队列对性能进行了优化；
2.如果两站间存在多条最短路径，则输出其中的一条即可；

本次项目实现采用了flask作为后端提供接口服务，使用androidApp进行get请求获得数据，显示在Textview中

设计需求

确定储存地铁站文件的格式文件 （已确认使用json格式和文本格式）

确定读取地铁站数据的方式 （使用python的file打开命令）

确定获取两站点最小站点数的算法方式

进行外表封装

进行输出格式的确定

性能测试

最后结果检查

数据存储格式

stationline.txt文本为存储的地图数据文本，格式如下图所示：

使用0与1来分别表示是否需要换乘

地铁线路条数 线路x 线路x站数 站名1 是否需要换乘 站名2 是否需要换乘 ...

数据示例

2 20 曹庄 0 卞兴 0 芥园西道 0 咸阳路 0 长虹公园 1 广开四马路 0 西南角 1 鼓楼 0 东南角 0 建国道 0 天津站 1 远洋国际中心 0 顺驰桥 0 靖江路 1 翠阜新村 0 屿东城 0 登州路 0 国山路 0 数据文本读取代码 with open(os.path.join(os.path.abspath('..'), "station/stationLine.txt"), "r") as f: TOTAL = f.readline() for line in f.readlines(): if line != '\n': line = line.rstrip('\n') line = line.split(' ') if line[0] in LINEDATA: linei = line[0] continue line[1] = linei line0 = line[0] intline = int(line[1]) if intline not in data.keys(): data[intline] = [] data[intline].append(line0) else: data[intline].append(line0) if line0 not in datanum.keys(): datanum[line0] = [intline] else: datanum[line0].append(intline)

打印结果

stationline {"1": ["刘园", "西横堤", "果酒厂", "本溪路", "勤俭道", "洪湖里", "西站", "西北角", ..]} linesdata {"刘园": [1], "西横堤": [1], "果酒厂": [1], "本溪路": [1], "勤俭道": [1], "洪湖里": [1], "西站": [1, 6], "西北角": [1], "西南角": [1, 2], "二纬路": [1], "海光寺": [1], "鞍山道": [1], "营口道": [1, 3], "小白楼": [1], "下瓦房": [1, 5],....} station_num {"刘园": 0, "西横堤": 1, "果酒厂": 2, "本溪路": 3, "勤俭道": 4, "洪湖里": 5, "西站": 6, "西北角": 7, "西南角": 8, "二纬路": 9, "海光寺": 10, "鞍山道": 11, "营口道": 12, "小白楼": 13, "下瓦房": 14,.....}

获得点与点之间的最短路径:

def find_shortest_path(graph, start, end, path=[]): # 查找最短路径 path = path + [start] if start == end: return path if not start in graph.keys(): return None shortest = None for node in graph[start]: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest def find_all_paths(graph, start, end, path): # 查找所有的路径 path = path + [start] if start == end: return [path] if not start in graph.keys(): return [] paths = [] for node in graph[start]: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths pathss = {} for i in range(I): for j in range(I): if RouteGraph.get_edge(i, j) == 1: start = STATIO[i] end = STATIO[j] if i not in pathss.keys(): pathss[i] = [j] else: pathss[i].append(j) # pathss是记录每个站点接触的站点list # print(pathss)

dijkstra算法具体分析

def dijkstra_shortest_pathS(graph, v0, endpos): vnum = 0 for i in pathss.keys(): vnum += 1 assert 0 <= v0 < vnum # 长为vnum的表记录路径 paths = [None] * vnum count = 0 cands = PrioQueue([(0, v0, v0)]) while count < vnum and not cands.is_empty(): plen, u, vmin = cands.dequeue() if paths[vmin]: continue paths[vmin] = (u, plen) # print(u, plen) for v in graph[vmin]: if not paths[v]: cands.enqueue((plen + 1, vmin, v)) count += 1 return paths

stationController 部分

# encoding=utf-8 import os import json from stationplan import computefshortestpath from stationplan import getInfo def getShort(start, end): stationnum, s = computefshortestpath(start, end) return stationnum, s def getInfoStation(): stationnumlist, stationlist = getInfo() return stationnumlist, stationlist if __name__ == "__main__": a, b = getInfoStation() print(type(a)) print(type(b))

stationController中具体使用的函数分析

# 确定出发点和最后的站点 def computefshortestpath(startpos, endpos): s1 = STATION_NUM[startpos] e1 = STATION_NUM[endpos] # print(s1,e1) paths = dijkstra_shortest_pathS(pathss, s1, e1) # print(paths) b = [] p = paths[e1][0] # print(paths[e1]) b.append(STATIO[p]) while True: p1 = paths[p][0] p = p1 b.append(STATIO[p]) if p == s1: break b.reverse() if s1 != e1: b.append(STATIO[e1]) stationnumo = len(b) s = "" s += b[0] for i in range(1, len(b) - 1): a1 = set(datanum[b[i - 1]]) b1 = set(datanum[b[i + 1]]) c1 = set(datanum[b[i]]) # 如果没有交集，说明不是同一条路,对当前站点前后站点进行分析，如果两个站点属于 # 的站点线号没有发生重叠，说明当前线路在该站点没有进行换乘 if not len(a1 & b1): if len(datanum[b[i + 1]]) != 0: s += "-" + str((list(set(datanum[b[i]]) & b1)[0])) + "号线" s += "-" + b[i] else: s += "-" + b[i] s += "-" + b[len(b) - 1] return stationnumo, s def getInfo(): return data, STATION_NUM flask app的分析：

flask具体作用类似与springboot，是python后端的一个框架，对新手及其友好，而json包则是用来处理json输出格式的一个工具