北京地铁计价

起因

因为某人的离散期末作业，开始的这个项目，自己也想学习一些算法知识，也拿来实践实践，运用出来。废话不多说，开始。

核心算法

迪杰斯特拉算法（英语：Dijkstra’s algorithm）由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。

算法描述

迪杰斯特拉算法采用的是一种贪心策略。这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 m 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v，若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v的最短路径，或者如果路径不存在的话是无穷大。

下面的伪代码计算并保留图G中原点s到每一顶点v的最短距离d[v]，同时找出并保留v在此最短路径上的“前趋”，即沿此路径由s前往v，到达v之前所到达的顶点。其中，函数Extract_Min(Q) 将顶点集合Q中有最小d[u]值的顶点u从Q中删除并返回u。

function Dijkstra(G, w, s)
    for each vertex v in V[G]               // 初始化
        d[v] := infinity                    // 将各点的已知最短距离先设成无穷大
        previous[v] := undefined            // 各点的已知最短路径上的前趋都未知

    // 因为出发点到出发点间不需移动任何距离，所以可以直接将s到s的最小距离设为0
    d[s] := 0                        
    S := empty set
    Q := set of all vertices
    while Q is not an empty set             // Dijkstra算法主体
            u := Extract_Min(Q)
            S.append(u)
            for each edge outgoing from u as (u,v)
                if d[v] > d[u] + w(u,v)     // 拓展边（u,v）。w(u,v)为从u到v的路径长度。
                    d[v] := d[u] + w(u,v)   // 更新路径长度到更小的那个和值。
                    previous[v] := u        // 纪录前趋顶点

算法示例

目标实现

爬取北京地铁站间距离数据，生成一张无向图。通过迪杰斯特拉算法计算出两站的最短路径，用这个路径距离来计算出该程的票价。

数据爬取

谷歌搜索北京地铁站间公里数，发现北京地铁官网就有数据，F12审查网页，发现都是静态页面，非常好爬取。省了不少事，原本以为是最头疼的一步轻松地就解决了。

不过感觉可能因为很少人用了？CSS文件都加载不出来，官网首页也找不到有站间距离的链接，好像被废弃了。不过有数据就成了。

开始撸代码，这里爬虫用的是python的requests库，html解析用的是etree库，没其他原因，主要还是这两个库自更熟悉一点。相比其他爬虫库感觉更加简洁。

由于是很简单的爬虫，没有什么难度，直接上代码。

import os
import requests
from lxml import etree

r = requests.get("https://www.bjsubway.com/station/zjgls/")
r.encoding = r.apparent_encoding
text = r.text
html = etree.HTML(text)
example = '//*[contains(concat("",@class,""),"line_place")]//tbody//tr'
result = html.xpath(example)
textName = 'distance.txt'
f = open(textName,'w')
for trs in result:
    a = 0
    for n in trs:
        a += 1;
        if a == 1:
            str = n.text.split('――')
            for z in str:
                f.write(z+'\n')
        if a == 2:
            f.write(n.text+'\n')
f.close()

写的可能不是很规范，不过能用就行。得到一个九百多行的txt文件，三行一组，每一组包含了两站之间的距离。

这里我的“产品经理”提了个很奇怪的需求（小声BB）需要每一站的输入都要是英文，当时非常崩溃，不知道怎么去找这些站的标准英文名，还打算先把这些站名先转换成拼音再找特例一个个去改。不过幸好，在北京地铁的英文官网上，发现了他会获取一个有北京地铁站中英名对照的的xml。

感动，遂又写了个简单的小爬虫，代码就不放了。通过爬取建立了一个dict，然后对刚刚的数据站名一一查询改成相应的英文站名。中间发生过几次报错，恰好了解到了北京地铁一些小故事，挺有意思的，不过这都是后话了，后面再聊。

核心代码

读取刚刚爬取获得的站间距离数据，用邻接表来表示北京地铁线路图。再运用上述所讲的迪杰斯特拉算法建算出输入两个站的最短距离，按北京地铁收费方法计算出该车程的费用。下面是核心代码截图，好像还有挺多问题的，以待优化。

后记

这个小项目算是比较顺利的完成了，某人的离散数学期末作业至少代码部分算是满分通过吧=0=（毕竟老师只要求做四条线路的）迪杰斯特拉算法也是一个比较简单、基础的算法吧，不过这一次和实际结合还是非常有意思，感觉也挺有意义的。

本项目难点也不在算法上，而是数据的获取，本文大量篇幅也是在写爬取数据的部分。嘿嘿，本来核心代码部分是要拿c写一遍的，不过之前写爬虫祭出了python，就想偷懒用python写到底了。总之实践了一遍图的实现和最短路径算法，收获也挺多的。还是感谢某人提供的这次机会23333

起因