项目目的为开发一个北京地铁系统的路径查询系统，用户通过输入出发地和目的地，得到最优的出行方案。源代码：github

　　本人选择使用网页形式向用户呈现结果，采用的web框架为：tornado。参考链接：Tornado

　　算法上选择了Dijkstra算法，由于站点间的实际距离数据难以获得，构建图时将临近站点距离视为1个单位。参考链接：Dijkstra

　　出发地和目的地的选择：

　　 

　　返回查找路径结果：

　　　　　　

 

 

 

 

 

 

 

 

 

 

　　根据需求，所有站点和线路的信息存放在station.txt文件。为方便读取和数据处理，station.txt文件中的格式修改为：

  1. 总线路数
  2. 线路1 数目1
  3. 站点1-1 是否换乘
  4. 站点1-2 是否换乘
  5. ……
  6. 线路2 数目2
  7. 站点2-1 是否换乘
  8. 站点2-2 是否换乘
  9. ……
  10. 线路n 数目n
  11. 站点n-1 是否换乘
  12. 站点n-2 是否换乘
  13. ……

　　以北京目前拥有的24条地铁线路为例，station.txt的部分截图（0表示为不可换乘站，1表示可换乘站）如下图所示:

　　 

　　处理后的数据存放在字典中：

 　　

　　得到所有站点数据后就需要创建图。在创建图时会发现，若以领接矩阵形式存放数据，会有大量空间浪费，因为换乘站占总站数的比例很小。所以考虑使用领接表效率更高。

　　

  1. class GraphAL(Graph):
  2.     def __init__(self,mat=[],unconn=0):
  3.         vnum=len(mat)
  4.         for x in mat:
  5.             if len(x)!=vnum:
  6.                 raise ValueError("Argument for \'GraphAL\'.")
  7.         self._mat=[Graph._out_edges(mat[i],unconn) for i in range(vnum)]
  8.         self._vnum=vnum
  9.         self._unconn=unconn
  10.     def add_vertex(self):#增加新节点时安排一个新编号
  11.         self._mat.append([])
  12.         self._vnum+=1
  13.         return self._vnum-1
  14.     def add_edge(self,vi,vj,val=1):
  15.         if self._vnum==0:
  16.             raise GraphError("cannot add edge to empty graph")
  17.         if self._invalid(vi) or self._invalid(vj):
  18.             raise GraphError(str(vi) + \' or \' + str(vj) + " is not a valid vertex.")
  19.         row=self._mat[vi]
  20.         i=0
  21.         while i<len(row):
  22.             if row[i][0]==vj:#更新mat[vi][vj]的值
  23.                 self._mat[vi][i]=(vj,val)
  24.                 return
  25.             if row[i][0]>vj:#原来如果没有到vj的边，退出循环，加入边
  26.                 break
  27.             i+=1
  28.         self._mat[vi].insert(i,(vj,val))
  29.     def get_edge(self,vi,vj):
  30.         if self._invalid(vi) or self._invalid(vj):
  31.             raise GraphError(str(vi) + \' or \' + str(vj) + " is not a valid vertex.")
  32.         for i,val in self._mat[vi]:
  33.             if i==vj:
  34.                 return val
  35.         return self._unconn
  36.     def out_edges(self,vi):
  37.         if self._invalid(vi):
  38.             raise GraphError(str(vi)+" is not a valid vertex.")
  39.         return self._mat[vi]

　　在后端核心的寻找路径代码上，选择了Dijkstra算法。Dijkstra用于求图中指定两点之间的最短路径，或者是指定一点到其它所有点之间的最短路径，实质上是贪心算法。

　　寻找最短路径代码：

  1. def dijkstra_shortest_pathS(graph,v0,endpos):
  2.     vnum=0
  3.     for i in pathss.keys():
  4.         vnum+=1
  5.     assert 0<=v0<vnum
  6.     paths=[None]*vnum#长为vnum的表记录路径
  7.     count=0
  8.     cands=PrioQueue([(0,v0,v0)])#求解最短路径的候选边集记录在优先队列cands中（p,v,v\'）v0经过v到v\'的最短路径长度为p，根据p的大小排序，保证选到最近的未知距离顶点
  9.     while count<vnum and not cands.is_empty():
  10.         plen,u,vmin=cands.dequeue()#取路径最短顶点
  11.         if paths[vmin]:#如果这个点的最短路径已知，则跳过
  12.             continue
  13.         paths[vmin]=(u,plen)#新确定最短路径并记录
  14.         for v in graph[vmin]:#遍历经过新顶点组的路径
  15.             if not paths[v]:#如果还不知道最短路径的顶点的路径，则记录
  16.                 cands.enqueue((plen+1,vmin,v))
  17.         count+=1
  18.     return paths

　　前端上选择了轻量级的tornado框架，该框架的优点有：

  • 抗负载性强
  • 异步非阻塞IO处理方式
  • 优异的处理性能，不依赖多进程/多线程，一定程度上解决C10K问题
  • WSGI全栈替代产品，推荐同时使用其web框架和HTTP服务器

　　该项目设计了两个页面，一个是主页面，即查询页面（testUI.html），另一个是结果展示页面（index.html）。

　　前后端交互的整体思路为：

  1. 后端向前端发送线路及站点信息，前端通过多选框形式展示给用户
  2. 前端将用户选择的出发地和目的地发送给后端处理
  3. 后端将得到的线路查询结果发送给前端，前端渲染后返回给用户

　　框架上开启了8080端口，使用者可运行app.py后在chrome输入127.0.0.1:8080 进行操作。代码如下：

  1. from tornado import web,ioloop,httpserver
  2. import findPath
  3. data=findPath.data
  4. RESULT=\'test\'
  5.  
  6. class MainPageHandler(web.RequestHandler):
  7.     def get(self, *args, **kwargs):
  8.         self.render(\'testUI.html\',data=data,result=\'\')
  9.     def post(self, *args, **kwargs):
  10.         startPos = self.get_argument(\'startPos\')
  11.         endPos = self.get_argument(\'endPos\')
  12.         if startPos and endPos:
  13.             global RESULT
  14.             RESULT = findPath.getPath(startPos, endPos)
  15.             self.redirect(\'/index\')
  16.         else:
  17.             self.write(\'内容不能为空\')
  18.  
  19. class ShowResultHandler(web.RequestHandler):
  20.     def get(self, *args, **kwargs):
  21.         self.render(\'index.html\',result=RESULT)
  22.     def post(self, *args, **kwargs):
  23.         self.redirect(\'/\')
  24.  
  25. settings = {
  26.     \'template_path\':\'templates\',
  27.     \'static_path\':\'static\'
  28. }
  29.  
  30. application = web.Application([
  31.             (r"/", MainPageHandler),
  32.             (r"/index", ShowResultHandler),
  33.         ], **settings)
  34.  
  35. if __name__ == \'__main__\':
  36.     http_server = httpserver.HTTPServer(application)
  37.     http_server.listen(8080)
  38.     ioloop.IOLoop.current().start()

　　testUI.html代码如下：

  1. <!DOCTYPE html>
  2. <!-- saved from url=(0039)https://v3.bootcss.com/examples/signin/ -->
  3. <html lang="zh-CN">
  4. <head>
  5.     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  6.     <meta http-equiv="X-UA-Compatible" content="IE=edge">
  7.     <meta name="viewport" content="width=device-width, initial-scale=1">
  8.     <meta name="description" content="">
  9.     <meta name="author" content="">
  10.     <link rel="icon" href="https://v3.bootcss.com/favicon.ico">
  11.     <title>Beijing Metro</title>
  12.     <!-- Bootstrap core CSS -->
  13.     <link href="/static/css/bootstrap.min.css" rel="stylesheet">
  14.     <!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
  15.     <link href="/static/css/ie10-viewport-bug-workaround.css" rel="stylesheet">
  16.     <!-- Custom styles for this template -->
  17.     <link href="/static/css/signin.css" rel="stylesheet">
  18.     <!-- Just for debugging purposes. Don\'t actually copy these 2 lines! -->
  19.     <!--[if lt IE 9]><script src="../../assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
  20.     <script src="/static/js/ie-emulation-modes-warning.js"></script>
  21.     <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
  22.     <!--[if lt IE 9]>
  23.       <script src="https://cdn.bootcss.com/html5shiv/3.7.3/html5shiv.min.js"></script>
  24.       <script src="https://cdn.bootcss.com/respond.js/1.4.2/respond.min.js"></script>
  25.     <![endif]-->
  26.   </head>
  27.   <body>
  28.     <div class="container">
  29.       <form class="form-signin" method="post">
  30.         <h2 class="form-signin-heading">选择地点</h2>
  31.         <div class="start">
  32.             <label for="startPos">出发地</label>
  33.             <select id="startLine" class="form-control" onchange="changeStart({{ data }})">
  34.                 <option class="option" value="1" select="selected">1号线</option>
  35.                 <option class="option" value="2">2号线</option>
  36.                 <option class="option" value="4">4号线</option>
  37.                 <option class="option" value="5">5号线</option>
  38.                 <option class="option" value="6">6号线</option>
  39.                 <option class="option" value="7">7号线</option>
  40.                 <option class="option" value="8S">8号线南</option>
  41.                 <option class="option" value="8N">8号线北</option>
  42.                 <option class="option" value="9">9号线</option>
  43.                 <option class="option" value="10">10号线</option>
  44.                 <option class="option" value="13">13号线</option>
  45.                 <option class="option" value="14E">14号线东</option>
  46.                 <option class="option" value="14W">14号线西</option>
  47.                 <option class="option" value="15">15号线</option>
  48.                 <option class="option" value="16">16号线</option>
  49.                 <option class="option" value="S1">S1号线</option>
  50.                 <option class="option" value="S2">S2号线</option>
  51.                 <option class="option" value="bt">八通线</option>
  52.                 <option class="option" value="cp">昌平线</option>
  53.                 <option class="option" value="fs">房山线</option>
  54.                 <option class="option" value="sdjc">首都机场线</option>
  55.                 <option class="option" value="xj">西郊线</option>
  56.                 <option class="option" value="yf">燕房线</option>
  57.                 <option class="option" value="yz">亦庄线</option>
  58.             </select>
  59.             <select id="startPos" name="startPos" class="form-control">
  60.                 {% for pos in data[1] %}
  61.                     <option>{{ pos }}</option>
  62.                 {% end %}
  63.             </select>
  64.             <label></label>
  65.         </div>
  66.         <div class="end">
  67.             <label for="endPos">目的地</label>
  68.             <select id="endLine" class="form-control" onchange="changeEnd({{ data }})">
  69.                 <option class="option" value="1" select="selected">1号线</option>
  70.                 <option class="option" value="2">2号线</option>
  71.                 <option class="option" value="4">4号线</option>
  72.                 <option class="option" value="5">5号线</option>
  73.                 <option class="option" value="6">6号线</option>
  74.                 <option class="option" value="7">7号线</option>
  75.                 <option class="option" value="8S">8号线南</option>
  76.                 <option class="option" value="8N">8号线北</option>
  77.                 <option class="option" value="9">9号线</option>
  78.                 <option class="option" value="10">10号线</option>
  79.                 <option class="option" value="13">13号线</option>
  80.                 <option class="option" value="14E">14号线东</option>
  81.                 <option class="option" value="14W">14号线西</option>
  82.                 <option class="option" value="15">15号线</option>
  83.                 <option class="option" value="16">16号线</option>
  84.                 <option class="option" value="S1">S1号线</option>
  85.                 <option class="option" value="S2">S2号线</option>
  86.                 <option class="option" value="bt">八通线</option>
  87.                 <option class="option" value="cp">昌平线</option>
  88.                 <option class="option" value="fs">房山线</option>
  89.                 <option class="option" value="sdjc">首都机场线</option>
  90.                 <option class="option" value="xj">西郊线</option>
  91.                 <option class="option" value="yf">燕房线</option>
  92.                 <option class="option" value="yz">亦庄线</option>
  93.             </select>
  94.             <select id="endPos" name="endPos" class="form-control">
  95.                 {% for pos in data[1] %}
  96.                     <option>{{ pos }}</option>
  97.                 {% end %}
  98.             </select>
  99.             <label></label>
  100.         </div>
  101.         <button class="btn btn-lg btn-primary btn-block" type="submit")>查询</button>
  102.       </form>
  103.     </div>
  104.     <!-- /container -->
  105.     <!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
  106.     <script src="/static/js/ie10-viewport-bug-workaround.js"></script>
  107.     <script>
  108.         function changeStart(data)
  109.         {
  110.             var line = document.getElementById(\'startLine\')
  111.             var pos = document.getElementById(\'startPos\')
  112.             pos.options.length=0
  113.             L = line.selectedIndex + 1
  114.             for (item in data[L]){
  115.                 pos.options.add(new Option(data[L][item]))
  116.             }
  117.         }
  118.         function changeEnd(data)
  119.         {
  120.             var line = document.getElementById(\'endLine\')
  121.             var pos = document.getElementById(\'endPos\')
  122.             pos.options.length=0
  123.             L = line.selectedIndex + 1
  124.             for (item in data[L]){
  125.                 pos.options.add(new Option(data[L][item]))
  126.             }
  127.         }
  128.     </script>
  129. </body></html>

　　index.html代码如下：

  1. <!DOCTYPE html>
  2. <html lang="zh-CN">
  3. <head>
  4.     <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  5.     <meta http-equiv="X-UA-Compatible" content="IE=edge">
  6.     <meta name="viewport" content="width=device-width, initial-scale=1">
  7.     <meta name="description" content="">
  8.     <meta name="author" content="">
  9.     <link rel="icon" href="https://v3.bootcss.com/favicon.ico">
  10.     <title>Beijing Metro</title>
  11.     <!-- Bootstrap core CSS -->
  12.     <link href="/static/css/bootstrap.min.css" rel="stylesheet">
  13.     <!-- IE10 viewport hack for Surface/desktop Windows 8 bug -->
  14.     <link href="/static/css/ie10-viewport-bug-workaround.css" rel="stylesheet">
  15.     <!-- Custom styles for this template -->
  16.     <link href="/static/css/signin.css" rel="stylesheet">
  17.     <!-- Just for debugging purposes. Don\'t actually copy these 2 lines! -->
  18.     <!--[if lt IE 9]><script src="../../assets/js/ie8-responsive-file-warning.js"></script><![endif]-->
  19.     <script src="/static/js/ie-emulation-modes-warning.js"></script>
  20.     <!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
  21.     <!--[if lt IE 9]>
  22.       <script src="https://cdn.bootcss.com/html5shiv/3.7.3/html5shiv.min.js"></script>
  23.       <script src="https://cdn.bootcss.com/respond.js/1.4.2/respond.min.js"></script>
  24.     <![endif]-->
  25.   </head>
  26. <body>
  27.     <div id="oDiv" class="container" align="center">
  28.         <form method="post">
  29.             <img src="http://jtapi.bendibao.com/ditie/inc/bj/xianluda.gif" width = \'750px\' height = \'562px\' >
  30.             <div>
  31.                 <label id="result" style="font-size:25px; color: #8c8c8c" ></label>
  32.             </div>
  33.             <div align="right">
  34.                 <button class="btn btn-lg btn-primary " type="submit")>返回</button>
  35.             </div>
  36.         </form>
  37.     </div>
  38.     <script>
  39.         var result = \'{% raw result %}\'
  40.         var label = document.getElementById(\'result\')
  41.         label.innerText = result
  42.     </script>
  43. </body>
  44. </html>

　　本项目的后端用python实现，核心代码采用Dijkstra算法，web框架选择了tornado。

　　该项目让我简单复习了图的构建和Dijkstra算法，感受到了在开发一个项目时，程序封装对后期维护和调试的重要性。

　　前端页面上使用了下拉框以避免用户的非法输入，同时也提高了使用体验。由于之前没有web前端开发的经验，通过自学后受益匪浅。

版权声明：本文为Dongtr原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Dongtr/p/11646945.html