本文通過我做過的一個小項目來分享一下如何通過BFS搜索算法實現北京地鐵換乘路線。搜索的規則分別為最短距離與最少換乘線路。BFS算法的原理這里就不講了，推薦一個B站的視頻，對搜索算法講解的很清晰：

BFS與DFS：https://www.bilibili.com/video/BV1Ks411575U

Dijkstra：https://www.bilibili.com/video/BV1ts41157Sy

首先是導入長長的各站地鐵的地理位置（怪我不熟悉爬蟲_(:з」∠)_）：

station_source = [{"name":"巴溝","lat":"116.294","lng":"39.9742"}, {"name":"蘇州街","lat":"116.306","lng":"39.9756"}, {"name":"海淀黃莊","lat":"116.318","lng":"39.976"}, {"name":"知春里","lat":"116.329","lng":"39.9763"}, {"name":"知春路","lat":"116.34","lng":"39.9765"}, {"name":"西土城","lat":"116.354","lng":"39.9762"}, {"name":"牡丹園","lat":"116.37","lng":"39.9763"}, {"name":"健德門","lat":"116.381","lng":"39.9767"}, {"name":"北土城","lat":"116.394","lng":"39.9769"}, {"name":"安貞門","lat":"116.406","lng":"39.977"}, {"name":"惠新西街南口","lat":"116.418","lng":"39.977"}, {"name":"芍藥居","lat":"116.436","lng":"39.9779"}, {"name":"太陽宮","lat":"116.448","lng":"39.9727"}, {"name":"三元橋","lat":"116.457","lng":"39.9614"}, {"name":"亮馬橋","lat":"116.462","lng":"39.9494"}, {"name":"農業展覽館","lat":"116.462","lng":"39.9416"}, {"name":"團結湖","lat":"116.462","lng":"39.9337"}, {"name":"呼家樓","lat":"116.462","lng":"39.9232"}, {"name":"金臺夕照","lat":"116.462","lng":"39.9167"}, {"name":"國貿","lat":"116.46","lng":"39.9084"}, {"name":"雙井","lat":"116.462","lng":"39.8935"}, {"name":"勁松","lat":"116.461","lng":"39.8844"}, {"name":"潘家園","lat":"116.461","lng":"39.8755"}, {"name":"十里河","lat":"116.458","lng":"39.8659"}, {"name":"分鐘寺","lat":"116.454","lng":"39.8519"}, {"name":"成壽寺","lat":"116.447","lng":"39.8459"}, {"name":"宋家莊","lat":"116.428","lng":"39.8457"}, {"name":"石榴莊","lat":"116.414","lng":"39.8459"}, {"name":"大紅門","lat":"116.399","lng":"39.8454"}, {"name":"角門東","lat":"116.385","lng":"39.8451"}, {"name":"角門西","lat":"116.371","lng":"39.8459"}, {"name":"草橋","lat":"116.351","lng":"39.8459"}, {"name":"紀家廟","lat":"116.333","lng":"39.8444"}, {"name":"首經貿","lat":"116.32","lng":"39.8445"}, {"name":"豐臺站","lat":"116.305","lng":"39.8499"}, {"name":"泥洼","lat":"116.304","lng":"39.8582"}, {"name":"西局","lat":"116.304","lng":"39.8665"}, {"name":"六里橋","lat":"116.303","lng":"39.8803"}, {"name":"蓮花橋","lat":"116.31","lng":"39.8977"}, {"name":"公主墳","lat":"116.31","lng":"39.9075"}, {"name":"西釣魚臺","lat":"116.298","lng":"39.9233"}, {"name":"慈壽寺","lat":"116.294","lng":"39.933"}, {"name":"車道溝","lat":"116.294","lng":"39.9481"}, {"name":"長春橋","lat":"116.294","lng":"39.9583"}, {"name":"火器營","lat":"116.289","lng":"39.966"}, {"name":"積水潭","lat":"116.373","lng":"39.9487"}, {"name":"鼓樓大街","lat":"116.394","lng":"39.948"}, {"name":"安定門","lat":"116.408","lng":"39.9492"}, {"name":"雍和宮","lat":"116.417","lng":"39.9487"}, {"name":"東直門","lat":"116.435","lng":"39.9424"}, {"name":"東四十條","lat":"116.434","lng":"39.9337"}, {"name":"朝陽門","lat":"116.433","lng":"39.9244"}, {"name":"建國門","lat":"116.436","lng":"39.9086"}, {"name":"北京站","lat":"116.427","lng":"39.905"}, {"name":"崇文門","lat":"116.419","lng":"39.9008"}, {"name":"前門","lat":"116.398","lng":"39.9002"}, {"name":"和平門","lat":"116.384","lng":"39.9001"}, {"name":"宣武門","lat":"116.374","lng":"39.8998"}, {"name":"長椿街","lat":"116.363","lng":"39.8994"}, {"name":"復興門","lat":"116.357","lng":"39.9072"}, {"name":"阜成門","lat":"116.356","lng":"39.9235"}, {"name":"車公莊","lat":"116.355","lng":"39.9324"}, {"name":"西直門","lat":"116.353","lng":"39.942"}, {"name":"西直門","lat":"116.353","lng":"39.942"}, {"name":"大鐘寺","lat":"116.345","lng":"39.9666"}, {"name":"知春路","lat":"116.34","lng":"39.9765"}, {"name":"五道口","lat":"116.338","lng":"39.9929"}, {"name":"上地","lat":"116.32","lng":"40.033"}, {"name":"西二旗","lat":"116.306","lng":"40.0531"}, {"name":"龍澤","lat":"116.319","lng":"40.0709"}, {"name":"回龍觀","lat":"116.336","lng":"40.0708"}, {"name":"霍營","lat":"116.361","lng":"40.0705"}, {"name":"立水橋","lat":"116.411","lng":"40.0527"}, {"name":"北苑","lat":"116.435","lng":"40.043"}, {"name":"望京西","lat":"116.447","lng":"39.995"}, {"name":"芍藥居","lat":"116.436","lng":"39.9779"}, {"name":"光熙門","lat":"116.432","lng":"39.9684"}, {"name":"柳芳","lat":"116.433","lng":"39.9583"}, {"name":"東直門","lat":"116.435","lng":"39.9424"}, {"name":"蘇莊","lat":"116.125","lng":"39.7233"}, {"name":"良鄉南關","lat":"116.141","lng":"39.7233"}, {"name":"良鄉大學城西","lat":"116.156","lng":"39.7232"}, {"name":"良鄉大學城","lat":"116.176","lng":"39.7232"}, {"name":"良鄉大學城北","lat":"116.184","lng":"39.73"}, {"name":"廣陽城","lat":"116.185","lng":"39.748"}, {"name":"籬笆房","lat":"116.19","lng":"39.7606"}, {"name":"長陽","lat":"116.213","lng":"39.7638"}, {"name":"稻田","lat":"116.219","lng":"39.7948"}, {"name":"大葆臺","lat":"116.291","lng":"39.8076"}, {"name":"郭公莊","lat":"116.302","lng":"39.8144"}, {"name":"南邵","lat":"116.287","lng":"40.2071"}, {"name":"沙河高教園","lat":"116.28","lng":"40.1647"}, {"name":"沙河","lat":"116.289","lng":"40.1483"}, {"name":"鞏華城","lat":"116.294","lng":"40.1309"}, {"name":"朱辛莊","lat":"116.314","lng":"40.1043"}, {"name":"生命科學園","lat":"116.294","lng":"40.0949"}, {"name":"西二旗","lat":"116.306","lng":"40.0531"}, {"name":"郭公莊","lat":"116.302","lng":"39.8144"}, {"name":"豐臺科技園","lat":"116.297","lng":"39.8252"}, {"name":"科怡路","lat":"116.298","lng":"39.8324"}, {"name":"豐臺南路","lat":"116.297","lng":"39.8414"}, {"name":"豐臺東大街","lat":"116.294","lng":"39.8553"}, {"name":"七里莊","lat":"116.294","lng":"39.8675"}, {"name":"六里橋","lat":"116.303","lng":"39.8803"}, {"name":"六里橋東","lat":"116.315","lng":"39.887"}, {"name":"北京西站","lat":"116.321","lng":"39.895"}, {"name":"軍事博物館","lat":"116.324","lng":"39.9074"}, {"name":"白堆子","lat":"116.326","lng":"39.9239"}, {"name":"白石橋南","lat":"116.325","lng":"39.933"}, {"name":"國家圖書館","lat":"116.325","lng":"39.9432"}, {"name":"四惠","lat":"116.496","lng":"39.9088"}, {"name":"四惠東","lat":"116.515","lng":"39.9085"}, {"name":"高碑店","lat":"116.532","lng":"39.9095"}, {"name":"傳媒大學","lat":"116.555","lng":"39.9092"}, {"name":"雙橋","lat":"116.577","lng":"39.9103"}, {"name":"管莊","lat":"116.599","lng":"39.9092"}, {"name":"八里橋","lat":"116.618","lng":"39.9059"}, {"name":"通州北苑","lat":"116.637","lng":"39.9037"}, {"name":"果園","lat":"116.646","lng":"39.8933"}, {"name":"九棵樹","lat":"116.658","lng":"39.8902"}, {"name":"梨園","lat":"116.668","lng":"39.8838"}, {"name":"臨河里","lat":"116.679","lng":"39.8754"}, {"name":"土橋","lat":"116.686","lng":"39.872"}, {"name":"蘋果園","lat":"116.178","lng":"39.9263"}, {"name":"古城","lat":"116.19","lng":"39.9074"}, {"name":"八角游樂園","lat":"116.213","lng":"39.9074"}, {"name":"八寶山","lat":"116.236","lng":"39.9074"}, {"name":"玉泉路","lat":"116.253","lng":"39.9074"}, {"name":"五棵松","lat":"116.274","lng":"39.9075"}, {"name":"萬壽路","lat":"116.295","lng":"39.9075"}, {"name":"公主墳","lat":"116.31","lng":"39.9075"}, {"name":"軍事博物館","lat":"116.324","lng":"39.9074"}, {"name":"木樨地","lat":"116.338","lng":"39.9074"}, {"name":"南禮士路","lat":"116.352","lng":"39.9072"}, {"name":"復興門","lat":"116.357","lng":"39.9072"}, {"name":"西單","lat":"116.376","lng":"39.9072"}, {"name":"天安門西","lat":"116.392","lng":"39.9075"}, {"name":"天安門東","lat":"116.402","lng":"39.9078"}, {"name":"王府井","lat":"116.412","lng":"39.9081"}, {"name":"東單","lat":"116.418","lng":"39.9083"}, {"name":"建國門","lat":"116.436","lng":"39.9086"}, {"name":"永安里","lat":"116.45","lng":"39.9085"}, {"name":"國貿","lat":"116.46","lng":"39.9084"}, {"name":"大望路","lat":"116.478","lng":"39.9083"}, {"name":"四惠","lat":"116.496","lng":"39.9088"}, {"name":"四惠東","lat":"116.515","lng":"39.9085"}, {"name":"宋家莊","lat":"116.428","lng":"39.8457"}, {"name":"肖村","lat":"116.448","lng":"39.8343"}, {"name":"小紅門","lat":"116.46","lng":"39.828"}, {"name":"舊宮","lat":"116.461","lng":"39.8071"}, {"name":"亦莊橋","lat":"116.48","lng":"39.803"}, {"name":"亦莊文化園","lat":"116.491","lng":"39.8068"}, {"name":"萬源街","lat":"116.505","lng":"39.8031"}, {"name":"榮京東街","lat":"116.513","lng":"39.7932"}, {"name":"榮昌東街","lat":"116.522","lng":"39.783"}, {"name":"同濟南路","lat":"116.54","lng":"39.7731"}, {"name":"經海路","lat":"116.562","lng":"39.7837"}, {"name":"次渠南","lat":"116.581","lng":"39.7951"}, {"name":"次渠","lat":"116.591","lng":"39.8034"}, {"name":"宋家莊","lat":"116.428","lng":"39.8457"}, {"name":"劉家窯","lat":"116.422","lng":"39.8576"}, {"name":"蒲黃榆","lat":"116.422","lng":"39.8657"}, {"name":"天壇東門","lat":"116.421","lng":"39.8831"}, {"name":"磁器口","lat":"116.419","lng":"39.8931"}, {"name":"崇文門","lat":"116.419","lng":"39.9008"}, {"name":"東單","lat":"116.418","lng":"39.9083"}, {"name":"燈市口","lat":"116.418","lng":"39.9172"}, {"name":"東四","lat":"116.417","lng":"39.9244"}, {"name":"張自忠路","lat":"116.417","lng":"39.9337"}, {"name":"北新橋","lat":"116.417","lng":"39.9409"}, {"name":"雍和宮","lat":"116.417","lng":"39.9487"}, {"name":"和平里北街","lat":"116.419","lng":"39.9587"}, {"name":"和平西橋","lat":"116.418","lng":"39.9685"}, {"name":"惠新西街南口","lat":"116.418","lng":"39.977"}, {"name":"惠新西街北口","lat":"116.417","lng":"39.9878"}, {"name":"大屯路東","lat":"116.417","lng":"40.0038"}, {"name":"北苑路北","lat":"116.418","lng":"40.0306"}, {"name":"立水橋南","lat":"116.415","lng":"40.0419"}, {"name":"立水橋","lat":"116.411","lng":"40.0527"}, {"name":"天通苑南","lat":"116.413","lng":"40.0664"}, {"name":"天通苑","lat":"116.413","lng":"40.0754"}, {"name":"天通苑北","lat":"116.413","lng":"40.0834"}, {"name":"焦化廠","lat":"116.536","lng":"39.85"}, {"name":"雙合","lat":"116.521","lng":"39.8575"}, {"name":"垡頭","lat":"116.512","lng":"39.8609"}, {"name":"歡樂谷景區","lat":"116.5","lng":"39.8685"}, {"name":"南樓梓莊","lat":"116.501","lng":"39.8748"}, {"name":"化工","lat":"116.507","lng":"39.8893"}, {"name":"百子灣","lat":"116.501","lng":"39.8931"}, {"name":"大郊亭","lat":"116.489","lng":"39.8932"}, {"name":"九龍山","lat":"116.478","lng":"39.8932"}, {"name":"廣渠門外","lat":"116.449","lng":"39.8936"}, {"name":"廣渠門內","lat":"116.435","lng":"39.8936"}, {"name":"磁器口","lat":"116.419","lng":"39.8931"}, {"name":"橋灣","lat":"116.406","lng":"39.8926"}, {"name":"珠市口","lat":"116.398","lng":"39.8912"}, {"name":"虎坊橋","lat":"116.385","lng":"39.8895"}, {"name":"菜市口","lat":"116.374","lng":"39.8893"}, {"name":"廣安門內","lat":"116.359","lng":"39.8894"}, {"name":"達官營","lat":"116.335","lng":"39.8899"}, {"name":"灣子","lat":"116.329","lng":"39.8898"}, {"name":"北京西站","lat":"116.321","lng":"39.895"}, {"name":"南鑼鼓巷","lat":"116.403","lng":"39.9331"}, {"name":"什剎海","lat":"116.396","lng":"39.9374"}, {"name":"鼓樓大街","lat":"116.394","lng":"39.948"}, {"name":"安華橋","lat":"116.395","lng":"39.9693"}, {"name":"北土城","lat":"116.394","lng":"39.9769"}, {"name":"奧體中心","lat":"116.394","lng":"39.9857"}, {"name":"奧林匹克公園","lat":"116.393","lng":"40.0023"}, {"name":"森林公園南門","lat":"116.393","lng":"40.01"}, {"name":"林萃橋","lat":"116.373","lng":"40.0219"}, {"name":"永泰莊","lat":"116.355","lng":"40.0376"}, {"name":"西小口","lat":"116.352","lng":"40.0469"}, {"name":"育新","lat":"116.347","lng":"40.0603"}, {"name":"霍營","lat":"116.361","lng":"40.0705"}, {"name":"回龍觀東大街","lat":"116.363","lng":"40.0812"}, {"name":"平西府","lat":"116.35","lng":"40.0906"}, {"name":"育知路","lat":"116.327","lng":"40.0878"}, {"name":"朱辛莊","lat":"116.314","lng":"40.1043"}, {"name":"天宮院","lat":"116.32","lng":"39.6702"}, {"name":"生物醫藥基地","lat":"116.322","lng":"39.6866"}, {"name":"義和莊","lat":"116.319","lng":"39.7125"}, {"name":"黃村火車站","lat":"116.333","lng":"39.723"}, {"name":"黃村西大街","lat":"116.333","lng":"39.7318"}, {"name":"清源路","lat":"116.333","lng":"39.7427"}, {"name":"棗園","lat":"116.332","lng":"39.7535"}, {"name":"高米店南","lat":"116.332","lng":"39.7635"}, {"name":"高米店北","lat":"116.331","lng":"39.7736"}, {"name":"西紅門","lat":"116.329","lng":"39.7896"}, {"name":"新宮","lat":"116.366","lng":"39.8123"}, {"name":"公益西橋","lat":"116.371","lng":"39.837"}, {"name":"角門西","lat":"116.371","lng":"39.8459"}, {"name":"馬家堡","lat":"116.371","lng":"39.8533"}, {"name":"北京南站","lat":"116.379","lng":"39.8652"}, {"name":"陶然亭","lat":"116.374","lng":"39.8786"}, {"name":"菜市口","lat":"116.374","lng":"39.8893"}, {"name":"宣武門","lat":"116.374","lng":"39.8998"}, {"name":"西單","lat":"116.376","lng":"39.9072"}, {"name":"靈境胡同","lat":"116.374","lng":"39.9161"}, {"name":"西四","lat":"116.373","lng":"39.9242"}, {"name":"平安里","lat":"116.372","lng":"39.9327"}, {"name":"新街口","lat":"116.368","lng":"39.9407"}, {"name":"西直門","lat":"116.353","lng":"39.942"}, {"name":"動物園","lat":"116.339","lng":"39.9383"}, {"name":"國家圖書館","lat":"116.325","lng":"39.9432"}, {"name":"魏公村","lat":"116.323","lng":"39.9578"}, {"name":"人民大學","lat":"116.321","lng":"39.9669"}, {"name":"海淀黃莊","lat":"116.318","lng":"39.976"}, {"name":"中關村","lat":"116.316","lng":"39.9839"}, {"name":"北京大學東門","lat":"116.316","lng":"39.9921"}, {"name":"圓明園","lat":"116.31","lng":"39.9995"}, {"name":"西苑","lat":"116.291","lng":"39.9983"}, {"name":"北宮門","lat":"116.278","lng":"40.0024"}, {"name":"安河橋北","lat":"116.27","lng":"40.0119"}, {"name":"T2航站樓","lat":"116.593","lng":"40.0795"}, {"name":"T3航站樓","lat":"116.616","lng":"40.0531"}, {"name":"三元橋","lat":"116.457","lng":"39.9614"}, {"name":"東直門","lat":"116.435","lng":"39.9424"}, {"name":"俸伯","lat":"116.685","lng":"40.1326"}, {"name":"順義","lat":"116.657","lng":"40.13"}, {"name":"石門","lat":"116.641","lng":"40.1299"}, {"name":"南法信","lat":"116.609","lng":"40.1284"}, {"name":"后沙峪","lat":"116.564","lng":"40.1141"}, {"name":"花梨坎","lat":"116.558","lng":"40.0844"}, {"name":"國展","lat":"116.555","lng":"40.0701"}, {"name":"孫河","lat":"116.535","lng":"40.0452"}, {"name":"馬泉營","lat":"116.504","lng":"40.0338"}, {"name":"崔各莊","lat":"116.493","lng":"40.0223"}, {"name":"望京東","lat":"116.487","lng":"40.0018"}, {"name":"望京","lat":"116.468","lng":"39.9973"}, {"name":"望京西","lat":"116.447","lng":"39.995"}, {"name":"關莊","lat":"116.428","lng":"40.0016"}, {"name":"安立路","lat":"116.408","lng":"40.0027"}, {"name":"奧林匹克公園","lat":"116.393","lng":"40.0023"}, {"name":"北沙灘","lat":"116.369","lng":"40.0015"}, {"name":"六道口","lat":"116.353","lng":"40.001"}, {"name":"清華東路西口","lat":"116.339","lng":"40.0007"}, {"name":"潞城","lat":"116.753","lng":"39.9014"}, {"name":"東夏園","lat":"116.736","lng":"39.9029"}, {"name":"郝家府","lat":"116.72","lng":"39.9024"}, {"name":"北運河東","lat":"116.704","lng":"39.902"}, {"name":"北運河西","lat":"116.69","lng":"39.9028"}, {"name":"通運門","lat":"116.677","lng":"39.91"}, {"name":"通州北關","lat":"116.66","lng":"39.9202"}, {"name":"物資學院路","lat":"116.639","lng":"39.9269"}, {"name":"草房","lat":"116.615","lng":"39.9244"}, {"name":"常營","lat":"116.6","lng":"39.9257"}, {"name":"黃渠","lat":"116.578","lng":"39.9242"}, {"name":"褡褳坡","lat":"116.563","lng":"39.924"}, {"name":"青年路","lat":"116.518","lng":"39.9232"}, {"name":"十里堡","lat":"116.502","lng":"39.9231"}, {"name":"金臺路","lat":"116.478","lng":"39.9229"}, {"name":"呼家樓","lat":"116.462","lng":"39.9232"}, {"name":"東大橋","lat":"116.452","lng":"39.9231"}, {"name":"朝陽門","lat":"116.433","lng":"39.9244"}, {"name":"東四","lat":"116.417","lng":"39.9244"}, {"name":"南鑼鼓巷","lat":"116.403","lng":"39.9331"}, {"name":"北海北","lat":"116.387","lng":"39.9333"}, {"name":"平安里","lat":"116.372","lng":"39.9327"}, {"name":"車公莊","lat":"116.355","lng":"39.9324"}, {"name":"車公莊西","lat":"116.344","lng":"39.9325"}, {"name":"白石橋南","lat":"116.325","lng":"39.933"}, {"name":"花園橋","lat":"116.31","lng":"39.9324"}, {"name":"慈壽寺","lat":"116.294","lng":"39.933"}, {"name":"海淀五路居","lat":"116.277","lng":"39.9326"}, {"name":"紅廟","lat":"116.478","lng":"39.9156"}, {"name":"大望路","lat":"116.478","lng":"39.9083"}, {"name":"九龍山","lat":"116.478","lng":"39.8932"}, {"name":"平樂園","lat":"116.477","lng":"39.8844"}, {"name":"松榆","lat":"116.477","lng":"39.8757"}, {"name":"南八里莊","lat":"116.47","lng":"39.8679"}, {"name":"十里河","lat":"116.458","lng":"39.8659"}, {"name":"方莊","lat":"116.433","lng":"39.8658"}, {"name":"蒲黃榆","lat":"116.422","lng":"39.8657"}, {"name":"安樂林","lat":"116.409","lng":"39.8651"}, {"name":"永定門外","lat":"116.399","lng":"39.8683"}, {"name":"陶然橋","lat":"116.388","lng":"39.8713"}, {"name":"北京南站","lat":"116.379","lng":"39.8652"}, {"name":"右安門外","lat":"116.365","lng":"39.8627"}, {"name":"西鐵營","lat":"116.354","lng":"39.8611"}, {"name":"菜戶營","lat":"116.343","lng":"39.8681"}, {"name":"麗澤商務區","lat":"116.336","lng":"39.8681"}, {"name":"東管頭","lat":"116.321","lng":"39.8679"}, {"name":"善各莊","lat":"116.476","lng":"40.0263"}, {"name":"來廣營","lat":"116.467","lng":"40.0206"}, {"name":"東湖渠","lat":"116.467","lng":"40.0102"}, {"name":"望京","lat":"116.468","lng":"39.9973"}, {"name":"阜通","lat":"116.47","lng":"39.9927"}, {"name":"望京南","lat":"116.478","lng":"39.9876"}, {"name":"高家園","lat":"116.489","lng":"39.9806"}, {"name":"將臺","lat":"116.49","lng":"39.9713"}, {"name":"東風北橋","lat":"116.487","lng":"39.9576"}, {"name":"棗營","lat":"116.474","lng":"39.9443"}, {"name":"朝陽公園","lat":"116.478","lng":"39.9337"}, {"name":"金臺路","lat":"116.478","lng":"39.9229"}, {"name":"西局","lat":"116.304","lng":"39.8665"}, {"name":"七里莊","lat":"116.294","lng":"39.8675"}, {"name":"大井","lat":"116.276","lng":"39.8652"}, {"name":"郭莊子","lat":"116.253","lng":"39.8644"}, {"name":"大瓦窯","lat":"116.24","lng":"39.8592"}, {"name":"園博園","lat":"116.202","lng":"39.8613"}, {"name":"張郭莊","lat":"116.187","lng":"39.8584"}]

建立站名與地理位置對應的dict：

station_info = {} for row in station_source:station_info[row['name']] = (float(row['lat']), float(row['lng']))print(station_info)

將所有站點存在一個list中：

station_list = list(station_info.keys()) print(station_list)

可視化一下看看：

import networkx as nx import matplotlib.pyplot as plt %matplotlib inlinestation_graph = nx.Graph() station_graph.add_nodes_from(station_list) nx.draw(station_graph, station_info, with_labels=True, node_size=3)

建立每個線路與其各個站點之間的dict：

line_2_station = {'房山線': ['蘇莊', '良鄉南關', '良鄉大學城西', '良鄉大學城', '良鄉大學城北', '廣陽城', '籬笆房', '長陽', '稻田', '大葆臺', '郭公莊'],'9號線': ['郭公莊', '豐臺科技園', '科怡路', '豐臺南路', '豐臺東大街', '七里莊', '六里橋', '六里橋東', '北京西站', '軍事博物館', '白堆子', '白石橋南', '國家圖書館'],'14號線西段': ['張郭莊', '園博園', '大瓦窯', '郭莊子', '大井', '七里莊', '西局'],'14號線東段': ['善各莊', '來廣營', '東湖渠', '望京', '阜通', '望京南', '高家園', '將臺', '東風北橋', '棗營', '朝陽公園', '金臺路', '大望路', '九龍山', '平樂園', '十里河', '方莊', '蒲黃榆', '永定門外', '北京南站'],'10號線': ['巴溝', '蘇州街', '海淀黃莊', '知春里', '知春路', '西土城', '牡丹園', '健德門', '北土城', '安貞門', '惠新西街南口', '芍藥居', '太陽宮', '三元橋', '亮馬橋', '農業展覽館', '團結湖', '呼家樓', '金臺夕照', '國貿', '雙井', '勁松', '潘家園', '十里河', '分鐘寺', '成壽寺', '宋家莊', '石榴莊', '大紅門', '角門東', '角門西', '草橋', '紀家廟', '首經貿', '豐臺站', '泥洼', '西局', '六里橋', '蓮花橋', '公主墳', '西釣魚臺', '慈壽寺', '車道溝', '長春橋', '火器營'],'6號線': ['潞城', '東夏園', '郝家府', '北運河東', '北運河西', '通運門', '通州北關', '物資學院路', '草房', '常營', '黃渠', '褡褳坡', '青年路', '十里堡', '金臺路', '呼家樓', '東大橋', '朝陽門', '東四', '南鑼鼓巷', '北海北', '平安里', '車公莊', '車公莊西', '白石橋南', '花園橋', '慈壽寺', '海淀五路居'],'4號線': ['天宮院', '生物醫藥基地', '義和莊', '黃村火車站', '黃村西大街', '清源路', '棗園', '高米店南', '高米店北', '西紅門', '新宮', '公益西橋', '角門西', '馬家堡', '北京南站', '陶然亭', '菜市口', '宣武門', '西單', '靈境胡同', '西四', '平安里', '新街口', '西直門', '動物園', '國家圖書館', '魏公村', '人民大學', '海淀黃莊', '中關村', '北京大學東門', '圓明園', '西苑', '北宮門', '安河橋北'],'13號線': ['西直門', '大鐘寺', '知春路', '五道口', '上地', '西二旗', '龍澤', '回龍觀', '霍營', '立水橋', '北苑', '望京西', '芍藥居', '光熙門', '柳芳', '東直門'],'昌平線': ['南邵', '沙河高教園', '沙河', '鞏華城', '朱辛莊', '生命科學園', '西二旗'],'8號線': ['南鑼鼓巷', '什剎海', '鼓樓大街', '什剎海', '安華橋', '北土城', '奧體中心', '奧林匹克公園', '森林公園南門', '林萃橋', '永泰莊', '西小口', '育新', '霍營', '回龍觀東大街', '平西府', '育知路'],'5號線': ['宋家莊', '劉家窯', '蒲黃榆', '天壇東門', '磁器口', '崇文門', '東單', '燈市口', '東四', '張自忠路', '北新橋', '雍和宮', '和平里北街', '和平西橋', '惠新西街南口', '惠新西街北口', '大屯路東', '北苑路北', '立水橋南', '立水橋', '天通苑南', '天通苑', '天通苑北'],'7號線': ['焦化廠', '雙合', '垡頭', '歡樂谷景區', '南樓梓莊', '化工', '百子灣', '大郊亭', '九龍山', '雙井', '廣渠門外', '廣渠門內','磁器口', '橋灣', '珠市口', '虎坊橋', '菜市口', '廣安門內', '達官營', '灣子', '北京西站'],'亦莊線': ['宋家莊', '肖村', '小紅門', '舊宮', '亦莊橋', '亦莊文化園', '萬源街', '榮京東街', '榮昌東街', '同濟南路', '經海路', '次渠南', '次渠'],'15號線': ['俸伯', '順義', '石門', '南法信', '后沙峪', '花梨坎', '國展', '孫河', '馬泉營', '崔各莊', '望京東', '望京', '關莊', '大屯路東', '安立路', '奧林匹克公園', '北沙灘', '六道口', '清華東路西口'],'2號線': ['積水潭', '鼓樓大街', '安定門', '雍和宮', '東直門', '東四十條', '朝陽門', '建國門', '北京站', '崇文門', '前門', '和平門', '宣武門', '長椿街', '復興門', '阜成門', '車公莊', '西直門'],'1號線': ['蘋果園', '古城', '八角游樂園', '八寶山', '玉泉路', '五棵松', '萬壽路', '公主墳', '軍事博物館', '木樨地', '南禮士路', '復興門', '西單', '天安門西', '天安門東', '王府井', '東單', '建國門', '永安里', '國貿', '大望路', '四惠', '四惠東', '高碑店', '傳媒大學', '雙橋', '管莊', '八里橋', '通州北苑', '果園', '九棵樹', '梨園', '臨河里', '土橋'] }

建立每個站點與其所屬的線路之間的dict：

from collections import defaultdictstation_2_line = defaultdict(list)for key in line_2_station.keys():line = line_2_station[key]for station in line:station_2_line[station].append(key) station_2_line

可以看到station_2_line是這樣滴：

接下來要建立每個站點與其相連的站點，比如與“東湖渠”連接的站點是“望京”和“來廣營”：

#建立每個站與其連接的所有站的dict station_connection = defaultdict(list) #每個站與其之前相連的站 for key in line_2_station.keys():for i in range(len(line_2_station[key])-1):station_connection[line_2_station[key][i]].append(line_2_station[key][i+1]) #每個站與其之后相連的站 for key in line_2_station.keys():for i in range(len(line_2_station[key])-1):station_connection[line_2_station[key][-i-1]].append(line_2_station[key][-i-2])

對于10號線這種環形線，還要手動補充一下：

#補充環狀線的連接站點 station_connection['巴溝'].append('火器營') station_connection['火器營'].append('巴溝') station_connection['積水潭'].append('西直門') station_connection['西直門'].append('積水潭')

現在我們可以看到站點與站點之間相連的dict：

接下來編寫一個計算地理位置距離的函數，輸入分別為兩個地點的經緯度：

import mathdef geo_distance(origin, destination):lat1, lon1 = originlat2, lon2 = destinationradius = 6371 # kmdlat = math.radians(lat2 - lat1)dlon = math.radians(lon2 - lon1)a = (math.sin(dlat / 2) * math.sin(dlat / 2) +math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) *math.sin(dlon / 2) * math.sin(dlon / 2))c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))d = radius * creturn d

以此編寫一個計算兩個站點之間的地理位置距離的函數：

#計算兩個站之間的直線距離 def get_station_distance(station1, station2):return geo_distance(station_info[station1], station_info[station2])

以此編寫一個計算一個列表中的所有站點之間的總距離的函數：

#計算一條路線的總距離 def get_distance_of_path(path: list):distance = 0for i, _ in enumerate(path[:-1]):distance += get_station_distance(path[i], path[i+1])return distance

以此編寫一個計算所有路線中距離最短的路線的函數：

#將所有可能的路線按距離排序，取最短距離的路線 def sort_by_distance(pathes: list):sorted_pathes = sorted(pathes, key=get_distance_of_path)return sorted_pathes

下面就是關鍵的BFS搜索算法，connection為相連站點之間的dict，start為起始站，destination為目標站，search_strategy為搜索策略，即按最短距離搜索還是按最少換乘路線搜索：

def BFS_by_distance(connection, start, destination, search_strategy=None):pathes = [[start]]while pathes:path = pathes.pop(0)#取到第一條線路的目前最后一站，找接下來所連接的站frontier = path[-1]#取到該站可能連接的所有站successsors = connection[frontier]for station in successsors:if station in path:continuenew_path = path + [station]pathes.append(new_path)if search_strategy:pathes = search_strategy(pathes)if pathes and destination==pathes[0][-1]:#計算換乘的路線lines = get_transfers_list(pathes[0])trans = lines[0]for x in lines[1:]:trans += ' --> ' + xstation_route = pathes[0][0]for x in pathes[0][1:]:station_route += ' --> ' + xreturn station_route, trans

現在我們想找到換乘次數最少的路線。

編寫一個函數，計算一條路線中所經過的所有不同地鐵線路：

# 得到途中所有經過的線路 def get_transfers_list(path: list):line_trans = []line = ''for i in np.arange(1, len(path)):# 這個判斷是處理換乘站，比如從1號線換到10號線時，換乘站既包含1號線也包含10號線if line in station_2_line[path[i]]:continuefirst_line = station_2_line[path[i-1]]second_line = station_2_line[path[i]]line = list(set(first_line).intersection(set(second_line)))[0]line_trans.append(line)return line_trans

編寫一個函數，計算換乘線路的數量：

def get_trans_times(path: list):return len(get_transfers_list(path)) - 1

編寫依據換乘路線數量的策略函數：

def sort_by_transfer_times(pathes: list):return sorted(pathes, key=get_trans_times)

看看“慈壽寺”到“菜市口”應該如何坐地鐵可以換乘次數最少：

BFS_by_distance(station_connection, '慈壽寺', '菜市口', search_strategy=sort_by_transfer_times)

可以看到此時從10號線——4號線只用換乘一次，但是經過的站數就變多了。

BFS_by_distance(station_connection, '國貿', '林萃橋', search_strategy=sort_by_transfer_times)

“國貿”到“林萃橋”此時也只用從10號線——8號線只用換乘一次。

讓我們更改一下搜索策略，看看“慈壽寺”到“菜市口”應該如何坐地鐵距離最短：

BFS_by_distance(station_connection, '慈壽寺', '菜市口', search_strategy=sort_by_distance)

可以看到根據最短距離策略，“慈壽寺”到“菜市口”要從10號線——1號線——2號線——4號線這樣坐地鐵是距離最短的。

再試試另外兩個站，看看從“國貿”到“林萃橋”如何坐地鐵距離最短：?

BFS_by_distance(station_connection, '國貿', '林萃橋', search_strategy=sort_by_distance)

“國貿”到“林萃橋”要從1號線——2號線——6號線——8號線這樣坐地鐵是距離最短的。其實還是換乘線路最少比較實用，哈哈。

那么以上就是通過BFS算法實現的一個小案例，感謝觀看！

?

---

?

?

總結

以上是生活随笔為你收集整理的运用BFS算法实现北京地铁路线换乘系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。