北京地铁线路查询 - 云吞面
北京地铁线路查询
项目概述
项目目的为开发一个北京地铁系统的路径查询系统，用户通过输入出发地和目的地，得到最优的出行方案。源代码：github
本人选择使用网页形式向用户呈现结果，采用的web框架为：tornado。参考链接：Tornado
算法上选择了Dijkstra算法，由于站点间的实际距离数据难以获得，构建图时将临近站点距离视为1个单位。参考链接：Dijkstra
运行截图
出发地和目的地的选择：
返回查找路径结果：
后端实现
根据需求，所有站点和线路的信息存放在station.txt文件。为方便读取和数据处理，station.txt文件中的格式修改为：
总线路数 线路1 数目1 站点1-1 是否换乘 站点1-2 是否换乘 …… 线路2 数目2 站点2-1 是否换乘 站点2-2 是否换乘 …… 线路n 数目n 站点n-1 是否换乘 站点n-2 是否换乘 ……
以北京目前拥有的24条地铁线路为例，station.txt的部分截图（0表示为不可换乘站，1表示可换乘站）如下图所示:
处理后的数据存放在字典中：
得到所有站点数据后就需要创建图。在创建图时会发现，若以领接矩阵形式存放数据，会有大量空间浪费，因为换乘站占总站数的比例很小。所以考虑使用领接表效率更高。
class GraphAL(Graph):
def __init__(self,mat=[],unconn=0):
vnum=len(mat)
for x in mat:
if len(x)!=vnum:
raise ValueError("Argument for \'GraphAL\'.")
self._mat=[Graph._out_edges(mat[i],unconn) for i in range(vnum)]
self._vnum=vnum
self._unconn=unconn
def add_vertex(self):#增加新节点时安排一个新编号
self._mat.append([])
self._vnum+=1
return self._vnum-1
def add_edge(self,vi,vj,val=1):
if self._vnum==0:
raise GraphError("cannot add edge to empty graph")
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + \' or \' + str(vj) + " is not a valid vertex.")
row=self._mat[vi]
i=0
while i<len(row):
if row[i][0]==vj:#更新mat[vi][vj]的值
self._mat[vi][i]=(vj,val)
return
if row[i][0]>vj:#原来如果没有到vj的边，退出循环，加入边
break
i+=1
self._mat[vi].insert(i,(vj,val))
def get_edge(self,vi,vj):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + \' or \' + str(vj) + " is not a valid vertex.")
for i,val in self._mat[vi]:
if i==vj:
return val
return self._unconn
def out_edges(self,vi):
if self._invalid(vi):
raise GraphError(str(vi)+" is not a valid vertex.")
return self._mat[vi]
在后端核心的寻找路径代码上，选择了Dijkstra算法。Dijkstra用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径，实质上是贪心算法。
寻找最短路径代码：
def dijkstra_shortest_pathS(graph,v0,endpos):
vnum=0
for i in pathss.keys():
vnum+=1
assert 0<=v0<vnum
paths=[None]*vnum#长为vnum的表记录路径
count=0
cands=PrioQueue([(0,v0,v0)])#求解最短路径的候选边集记录在优先队列cands中（p,v,v\'）v0经过v到v\'的最短路径长度为p，根据p的大小排序，保证选到最近的未知距离顶点
while count<vnum and not cands.is_empty():
plen,u,vmin=cands.dequeue()#取路径最短顶点
if paths[vmin]:#如果这个点的最短路径已知，则跳过
continue
paths[vmin]=(u,plen)#新确定最短路径并记录
for v in graph[vmin]:#遍历经过新顶点组的路径
if not paths[v]:#如果还不知道最短路径的顶点的路径，则记录
cands.enqueue((plen+1,vmin,v))
count+=1
return paths
前端实现
前端上选择了轻量级的tornado框架，该框架的优点有：
- 抗负载性强
- 异步非阻塞IO处理方式
- 优异的处理性能，不依赖多进程/多线程，一定程度上解决C10K问题
- WSGI全栈替代产品，推荐同时使用其web框架和HTTP服务器
该项目设计了两个页面，一个是主页面，即查询页面（testUI.html），另一个是结果展示页面（index.html）。
前后端交互的整体思路为：
- 后端向前端发送线路及站点信息，前端通过多选框形式展示给用户
- 前端将用户选择的出发地和目的地发送给后端处理
- 后端将得到的线路查询结果发送给前端，前端渲染后返回给用户
框架上开启了8080端口，使用者可运行app.py后在chrome输入127.0.0.1:8080 进行操作。代码如下：
from tornado import web,ioloop,httpserver
import findPath
data=findPath.data
RESULT=\'test\'
class MainPageHandler(web.RequestHandler):
def get(self, *args, **kwargs):
self.render(\'testUI.html\',data=data,result=\'\')
def post(self, *args, **kwargs):
startPos = self.get_argument(\'startPos\')
endPos = self.get_argument(\'endPos\')
if startPos and endPos:
global RESULT
RESULT = findPath.getPath(startPos, endPos)
self.redirect(\'/index\')
else:
self.write(\'内容不能为空\')
class ShowResultHandler(web.RequestHandler):
def get(self, *args, **kwargs):
self.render(\'index.html\',result=RESULT)
def post(self, *args, **kwargs):
self.redirect(\'/\')
settings = {
\'template_path\':\'templates\',
\'static_path\':\'static\'
}
application = web.Application([
(r"/", MainPageHandler),
(r"/index", ShowResultHandler),
], **settings)
if __name__ == \'__main__\':
http_server = httpserver.HTTPServer(application)
http_server.listen(8080)
ioloop.IOLoop.current().start()
testUI.html代码如下：
<!DOCTYPE html>
<!-- saved from url=(0039)https://v3.bootcss.com/examples/signin/ -->
<html lang="zh-CN">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="">
<meta name="author" content="">
<link rel="icon" href="https://v3.bootcss.com/favicon.ico">
<title>Beijing Metro</title>
<!-- Bootstrap core CSS -->
<link href="/static/css/bootstrap.min.css" rel="stylesheet">
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<link href="/static/css/ie10-viewport-bug-workaround.css" rel="stylesheet">
<!-- Custom styles for this template -->
<link href="/static/css/signin.css" rel="stylesheet">
<!-- Just for debugging purposes. Don\'t actually copy these 2 lines! -->
<!--[if lt IE 9]><script src="../../assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
<script src="/static/js/ie-emulation-modes-warning.js"></script>
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://cdn.bootcss.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://cdn.bootcss.com/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body>
<div class="container">
<form class="form-signin" method="post">
<h2 class="form-signin-heading">选择地点</h2>
<div class="start">
<label for="startPos">出发地</label>
<select id="startLine" class="form-control" onchange="changeStart({{ data }})">
<option class="option" value="1" select="selected">1号线</option>
<option class="option" value="2">2号线</option>
<option class="option" value="4">4号线</option>
<option class="option" value="5">5号线</option>
<option class="option" value="6">6号线</option>
<option class="option" value="7">7号线</option>
<option class="option" value="8S">8号线南</option>
<option class="option" value="8N">8号线北</option>
<option class="option" value="9">9号线</option>
<option class="option" value="10">10号线</option>
<option class="option" value="13">13号线</option>
<option class="option" value="14E">14号线东</option>
<option class="option" value="14W">14号线西</option>
<option class="option" value="15">15号线</option>
<option class="option" value="16">16号线</option>
<option class="option" value="S1">S1号线</option>
<option class="option" value="S2">S2号线</option>
<option class="option" value="bt">八通线</option>
<option class="option" value="cp">昌平线</option>
<option class="option" value="fs">房山线</option>
<option class="option" value="sdjc">首都机场线</option>
<option class="option" value="xj">西郊线</option>
<option class="option" value="yf">燕房线</option>
<option class="option" value="yz">亦庄线</option>
</select>
<select id="startPos" name="startPos" class="form-control">
{% for pos in data[1] %}
<option>{{ pos }}</option>
{% end %}
</select>
<label></label>
</div>
<div class="end">
<label for="endPos">目的地</label>
<select id="endLine" class="form-control" onchange="changeEnd({{ data }})">
<option class="option" value="1" select="selected">1号线</option>
<option class="option" value="2">2号线</option>
<option class="option" value="4">4号线</option>
<option class="option" value="5">5号线</option>
<option class="option" value="6">6号线</option>
<option class="option" value="7">7号线</option>
<option class="option" value="8S">8号线南</option>
<option class="option" value="8N">8号线北</option>
<option class="option" value="9">9号线</option>
<option class="option" value="10">10号线</option>
<option class="option" value="13">13号线</option>
<option class="option" value="14E">14号线东</option>
<option class="option" value="14W">14号线西</option>
<option class="option" value="15">15号线</option>
<option class="option" value="16">16号线</option>
<option class="option" value="S1">S1号线</option>
<option class="option" value="S2">S2号线</option>
<option class="option" value="bt">八通线</option>
<option class="option" value="cp">昌平线</option>
<option class="option" value="fs">房山线</option>
<option class="option" value="sdjc">首都机场线</option>
<option class="option" value="xj">西郊线</option>
<option class="option" value="yf">燕房线</option>
<option class="option" value="yz">亦庄线</option>
</select>
<select id="endPos" name="endPos" class="form-control">
{% for pos in data[1] %}
<option>{{ pos }}</option>
{% end %}
</select>
<label></label>
</div>
<button class="btn btn-lg btn-primary btn-block" type="submit")>查询</button>
</form>
</div>
<!-- /container -->
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<script src="/static/js/ie10-viewport-bug-workaround.js"></script>
<script>
function changeStart(data)
{
var line = document.getElementById(\'startLine\')
var pos = document.getElementById(\'startPos\')
pos.options.length=0
L = line.selectedIndex + 1
for (item in data[L]){
pos.options.add(new Option(data[L][item]))
}
}
function changeEnd(data)
{
var line = document.getElementById(\'endLine\')
var pos = document.getElementById(\'endPos\')
pos.options.length=0
L = line.selectedIndex + 1
for (item in data[L]){
pos.options.add(new Option(data[L][item]))
}
}
</script>
</body></html>
index.html代码如下：
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="">
<meta name="author" content="">
<link rel="icon" href="https://v3.bootcss.com/favicon.ico">
<title>Beijing Metro</title>
<!-- Bootstrap core CSS -->
<link href="/static/css/bootstrap.min.css" rel="stylesheet">
<!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
<link href="/static/css/ie10-viewport-bug-workaround.css" rel="stylesheet">
<!-- Custom styles for this template -->
<link href="/static/css/signin.css" rel="stylesheet">
<!-- Just for debugging purposes. Don\'t actually copy these 2 lines! -->
<!--[if lt IE 9]><script src="../../assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
<script src="/static/js/ie-emulation-modes-warning.js"></script>
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://cdn.bootcss.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://cdn.bootcss.com/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body>
<div id="oDiv" class="container" align="center">
<form method="post">
<img src="http://jtapi.bendibao.com/ditie/inc/bj/xianluda.gif" width = \'750px\' height = \'562px\' >
<div>
<label id="result" style="font-size:25px; color: #8c8c8c" ></label>
</div>
<div align="right">
<button class="btn btn-lg btn-primary " type="submit")>返回</button>
</div>
</form>
</div>
<script>
var result = \'{% raw result %}\'
var label = document.getElementById(\'result\')
label.innerText = result
</script>
</body>
</html>
总结
本项目的后端用python实现，核心代码采用Dijkstra算法，web框架选择了tornado。
该项目让我简单复习了图的构建和Dijkstra算法，感受到了在开发一个项目时，程序封装对后期维护和调试的重要性。
前端页面上使用了下拉框以避免用户的非法输入，同时也提高了使用体验。由于之前没有web前端开发的经验，通过自学后受益匪浅。
版权声明：本文为Dongtr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。