1. 引言

本此博文的完成是資料+演算法，資料部分是基于合肥本地寶和高德地圖提供的個人開發版api；演算法是基于Dijkstra，（所使用的工具是Python）

2. 匯入相應的模塊

各讀者可以根據自己PC運行報錯資訊，自行增加或洗掉相應模塊，

import itertools
import xlrd
from geopy.distance import geodesic
import xlwt
import requests
from bs4 import BeautifulSoup
import pandas as pd
import json
import os
from tqdm import tqdm
from collections import defaultdict
import pickle

3. 申請高德地圖的API

申請地址為：申請地址
申請步驟：
免費注冊（自行完成注冊）
進入控制臺
進入我的應用
創建新應用（筆者創建資訊如下，安全起見，給keynum打碼（這里的key對于能不能成功起著決定性作用），

這個時候，就獲得了高德題圖的key，為后面順利接入API奠定了基礎，

4. 獲取合肥地鐵資料

為了獲得合肥各個地鐵的地鐵站資訊，通過爬蟲爬取合肥各個地鐵站點的資訊，以及高德地圖提供的經緯度資訊，并存盤到xls檔案中（之所以存盤到xls檔案中，是因為原因是最近xlrd更新到了2.0.1版本，只支持.xls檔案,所以pd.read_excel(‘xxx.xlsx’)會報錯，)，下圖為合肥市最新的地鐵線路圖，

def spyder():
    #獲得合肥的地鐵資訊
    print('正在爬取合肥地鐵資訊...')
    url='http://hf.bendibao.com/ditie/linemap.shtml'
    user_agent='Opera/9.80 (Macintosh; Intel Mac OS X 10.6.8; U; en) Presto/2.8.131 Version/11.11'
    headers = {'User-Agent': user_agent}
    r = requests.get(url, headers=headers)
    r.encoding = r.apparent_encoding
    soup = BeautifulSoup(r.text, 'lxml')
    all_info = soup.find_all('div', class_='line-list')
    df=pd.DataFrame(columns=['name','site'])
    for info in tqdm(all_info):
        title=info.find_all('div',class_='wrap')[0].get_text().split()[0].replace('線路圖','')
        station_all=info.find_all('a',class_='link')
        for station in station_all:
            station_name=station.get_text()
            longitude,latitude=get_location(station_name,'合肥')
            temp={'name':station_name,'site':title,'longitude':longitude,'latitude':latitude}
            df =df.append(temp,ignore_index=True)
    df.to_excel('./hefei_subway.xls',index=False)

def get_location(keyword,city):
    #獲得經緯度資訊
    user_agent='Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_8; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 Safari/534.50'
    headers = {'User-Agent': user_agent}
    url='http://restapi.amap.com/v3/place/text?key='+keynum+'&keywords='+keyword+'&types=&city='+city+'&children=1&offset=1&page=1&extensions=all'
    data = requests.get(url, headers=headers)
    data.encoding='utf-8'
    data=json.loads(data.text)
    result=data['pois'][0]['location'].split(',')
    return result[0],result[1]

5. 計算合肥各地鐵站點之間的距離

高德地圖api提供了計算距離的介面，我們來構造計算距離的函式，然后輸入輸入經度和緯度就可以獲得距離，
代碼如下：

def compute_distance(longitude1,latitude1,longitude2,latitude2):
    #計算兩點之間的距離
    user_agent='Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_8; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 Safari/534.50'
    headers = {'User-Agent': user_agent}
    url='http://restapi.amap.com/v3/distance?key='+keynum+'&origins='+str(longitude1)+','+str(latitude1)+'&destination='+str(longitude2)+','+str(latitude2)+'&type=1'
    data=requests.get(url,headers=headers)
    data.encoding='utf-8'
    data=json.loads(data.text)
    result=data['results'][0]['distance']
    return result

pickle提供了一個簡單的持久化功能，可以將物件以檔案的形式存放在磁盤上，pickle模塊只能在python中使用，python中幾乎所有的資料型別（串列，字典，集合，類等）都可以用pickle來序列化，pickle序列化后的資料，可讀性差，人一般無法識別，但是，爬取資訊比較耗時，這里將制作好的圖網路保存為pickle檔案方便以后使用（無需給人看，電腦認識就行），

6.尋找最近的地鐵站

我們要去找距離最近的地鐵站首先是獲得位置的坐標；然后，將當前的坐標遍歷所有地鐵站找到最近的地鐵站，（代碼過多，這里就不貼了，如有需要請留言或者Email: mr.zhan9902@foxmail.com）

7. 運用Dijkstra演算法進行路徑規劃

關于Dijkstra演算法的介紹網上有很多資料，這里就不贅述，部分代碼如下：

#找到最短的路徑
def find_shortest_path(start,end,parents):
    node=end
    shortest_path=[end]
    #最終的根節點為start
    while parents[node] !=start:
        shortest_path.append(parents[node])
        node=parents[node]
    shortest_path.append(start)
    return shortest_path
#計算圖中從start到end的最短路徑
def dijkstra(start,end,graph,costs,processed,parents):
    #查詢到目前開銷最小的節點
    node=find_lowest_cost_node(costs,processed)
    #使用找到的開銷最小節點，計算它的鄰居是否可以通過它進行更新
    #如果所有的節點都在processed里面就結束
    while node is not None:
        #獲取節點的cost
        cost=costs[node]  #cost 是從node 到start的距離
        #獲取節點的鄰居
        neighbors=graph[node]
        #遍歷所有的鄰居，看是否可以通過它進行更新
        for neighbor in neighbors.keys():
            #計算鄰居到當前節點+當前節點的開銷
            new_cost=cost+float(neighbors[neighbor])
            if neighbor not in costs or new_cost<costs[neighbor]:
                costs[neighbor]=new_cost
                #經過node到鄰居的節點，cost最少
                parents[neighbor]=node
        #將當前節點標記為已處理
        processed.append(node)
        #下一步繼續找U中最短距離的節點  costs=U,processed=S
        node=find_lowest_cost_node(costs,processed)

    #回圈完成 說明所有節點已經處理完
    shortest_path=find_shortest_path(start,end,parents)
    shortest_path.reverse()
    return shortest_path

def subway_line(start,end):
    file=open('graph.pkl','rb')
    graph=pickle.load(file)
    #創建點之間的距離
    #現在我們有了各個地鐵站之間的距離存盤在graph
    #創建節點的開銷表，cost是指從start到該節點的距離
    costs={}
    parents={}
    parents[end]=None
    for node in graph[start].keys():
        costs[node]=float(graph[start][node])
        parents[node]=start
    #終點到起始點距離為無窮大
    costs[end]=float('inf')
    #記錄處理過的節點list
    processed=[]
    shortest_path=dijkstra(start,end,graph,costs,processed,parents)
    return shortest_path

8. 封裝打包

建立main檔案封裝所有函式，

def main(site1,site2):
    if not os.path.exists('./subway.xls'):
        spyder()
    if not os.path.exists('./graph.pkl'):
        get_graph()
    longitude1,latitude1=get_location(site1,'合肥')
    longitude2,latitude2=get_location(site2,'合肥')
    data=pd.read_excel('./hefei_subway.xls')
    #求最近的地鐵站
    start=get_nearest_subway(data,longitude1,latitude1)
    end=get_nearest_subway(data,longitude2,latitude2)
    shortest_path=subway_line(start,end)
    if site1 !=start:
        shortest_path.insert(0,site1)
    if site2 !=end:
        shortest_path.append(site2)
    print('根據Dijkstra演算法得出的出行路線為：\n','->\n'.join(shortest_path))

9. 是騾子是馬拉出來遛遛

比如，我現在處于合肥工業大學翡翠湖校區，要去合肥南站，我的路線該如何規劃？（假設只乘坐地鐵）
注意：下面的代碼中，keynum處需要輸入高德地圖分配的KEY號碼，
main檔案的引數不需要與官方地點名稱相同，比如，也可以輸成：合工大翡翠湖區等等，

if __name__ == '__main__':
    global keynum
    keynum='安全起見，這里就不輸入我的key了哈哈' #輸入自己的key
    main('合肥工業大學翡翠湖校區','合肥南站')

運行結果為：

即出行路線為：
合肥工業大學翡翠湖校區->工大翡翠湖校區->大學城北->繁華大道->安醫大二附院->省博物院->圖書館->合肥大劇院->市政務中心->洪崗->國防科技大學->西七里塘->五里墩->三里庵->安農大->三孝口->四牌樓->大東門->包公園->大南區->朱崗站->秋浦河路->葛大店->望湖城->合肥南站
然后，通過百度地圖搜索結果如下圖所示，與本規劃結果竟然一致哈哈（弄不好百度地圖用的也是Dijkstra哦，猜測而已，畢竟不能阻止其他演算法也得出同樣的結果呀哈哈），

本文參考了很多資料，非常感謝各位作者的貢獻（如有侵權，請聯系mr.zhan9902@foxmail.com）；歡迎各位看官一起交流、討論，共同學習、共同進步，