Shortest path between two cities and plotting [BFS, sorting] - Python solution

Foreword: Use Python for data processing, and draw the distribution map of major cities in my country through the support of third-party packages, and use BFS broad search priority search to calculate the shortest route between any two cities

Related Packages

``````import re   #regular expression package
import math   #math toolkit
import networkx as nx #networkx drawing package
import matplotlib   #matplotlib drawing package
import matplotlib .pyplot as plt
from collections import defaultdict
``````
• 1
• 2
• 3
• 4
• 5
• 6

data preparation

The following is the latitude and longitude information of some cities:

``````coordination_source =  """
{name:'Lanzhou', geoCoord:[103.73, 36.03]},
{name:'Jiayuguan', geoCoord:[98.17, 39.47]},
{name:'Xining', geoCoord:[101.74, 36.56]},
{name:'Chengdu', geoCoord:[104.06, 30.67]},
{name:'Shijiazhuang', geoCoord:[114.48, 38.03]},
{name:'Lhasa', geoCoord:[102.73, 25.04]},
{name:'Guiyang', geoCoord:[106.71, 26.57]},
{name:'Wuhan', geoCoord:[114.31, 30.52]},
{name:'Zhengzhou', geoCoord:[113.65, 34.76]},
{name:'Jinan', geoCoord:[117, 36.65]},
{name:'Nanjing', geoCoord:[118.78, 32.04]},
{name:'Hefei', geoCoord:[117.27, 31.86]},
{name:'Hangzhou', geoCoord:[120.19, 30.26]},
{name:'Nanchang', geoCoord:[115.89, 28.68]},
{name:'Fuzhou', geoCoord:[119.3, 26.08]},
{name:'Guangzhou', geoCoord:[113.23, 23.16]},
{name:'Changsha', geoCoord:[113, 28.21]},
//{name:'Haikou', geoCoord:[110.35, 20.02]},
{name:'Shenyang', geoCoord:[123.38, 41.8]},
{name:'Changchun', geoCoord:[125.35, 43.88]},
{name:'Harbin', geoCoord:[126.63, 45.75]},
{name:'Taiyuan', geoCoord:[112.53, 37.87]},
{name:'Xi'an', geoCoord:[108.95, 34.27]},
//{name:'Taiwan', geoCoord:[121.30, 25.03]},
{name:'Beijing', geoCoord:[116.46, 39.92]},
{name:'Shanghai', geoCoord:[121.48, 31.22]},
{name:'Chongqing', geoCoord:[106.54, 29.59]},
{name:'Tianjin', geoCoord:[117.2, 39.13]},
{name:'Hohhot', geoCoord:[111.65, 40.82]},
{name:'Nanning', geoCoord:[108.33, 22.84]},
//{name:'Tibet', geoCoord:[91.11, 29.97]},
{name:'Yinchuan', geoCoord:[106.27, 38.47]},
{name:'Urumqi', geoCoord:[87.68, 43.77]},
{name:'Hong Kong', geoCoord:[114.17, 22.28]},
{name:'Macau', geoCoord:[113.54, 22.19]}
"""
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37

data processing

Generally, the initial data is not easy to process, and there is a lot of information that we do not need, and the main information needs to be extracted

``````def  get_city_info ( city_coordination ) :
city_location =  { } #Split
the data with a newline
for line in city_coordination . split ( "\n" ) :
if line . startswith ( "//" ) :  continue #If   the string starts with "// ", skip
if line . strip ( )  ==  "" : continue #Remove    the leading and trailing null characters, if the returned empty string, return directly

#\w matches any alphanumeric character, same as [A-Za-z0-9_]
city = re . findall ( "name:'(\w+)'" , line ) [ 0 ]
#\d matches any decimal digit, Identical to [0-9]; \s matches any whitespace character
x_y = re . findall ( "Coord:\[(\d+.\d+),\s(\d+.\d+)\]" , line ) [ 0 ] #returns  a list, take the first element
# map converts the elements in x_y to floating-point data, and tuple converts it into a tuple
x_y =  tuple ( map ( float , x_y ) )
# store the result in dictionary city_location
city_location [ city ]  = x_y
return city_location
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

After the data is processed, print the write result:

``````city_info = get_city_info ( coordination_source )
print ( city_info )
``````
• 1
• 2
``````{'Lanzhou': (103.73, 36.03),
'Jiayuguan': (98.17, 39.47),
'Xining': (101.74, 36.56),
'Chengdu': (104.06, 30.67),
'Shijiazhuang': (114.48, 38.03),
'Lhasa': (102.73, 25.04),
'Guiyang': (106.71, 26.57),
'Wuhan': (114.31, 30.52),
'Zhengzhou': (113.65, 34.76),
'Jinan': (117.0, 36.65),
'Nanjing': (118.78, 32.04),
'Hefei': (117.27, 31.86),
'Hangzhou': (120.19, 30.26),
'Nanchang': (115.89, 28.68),
'Fuzhou': (119.3, 26.08),
'Guangzhou': (113.23, 23.16),
'Changsha': (113.0, 28.21),
'Shenyang': (123.38, 41.8),
'Changchun': (125.35, 43.88),
'Harbin': (126.63, 45.75),
'Taiyuan': (112.53, 37.87),
'Xi'an': (108.95, 34.27),
'Beijing': (116.46, 39.92),
'Shanghai': (121.48, 31.22),
'Chongqing': (106.54, 29.59),
'Tianjin': (117.2, 39.13),
'Hohhot': (111.65, 40.82),
'Nanning': (108.33, 22.84),
'Yinchuan': (106.27, 38.47),
'Urumqi': (87.68, 43.77),
'Hong Kong': (114.17, 22.28),
'Macau': (113.54, 22.19)}
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32

Calculate the distance between two cities

``````#The function input to calculate the distance between cities is the latitude and longitude information of the starting point and destination
def  geo_distance ( origin , destination ) :
"""
Calculate the Haversine distance.

Examples
--------
>>> origin = (48.1372, 11.5756) # Munich
>>> destination = (52.5186, 13.4083) # Berlin
>>> round(distance(origin, destination), 1)
504.2
"""
lat1 , lon1 = origin
lat2 , lon2 = destination

dlat = 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 ) )

return d

def  get_city_distance ( city1 , city2 ) :
return geo_distance ( city_info [ city1 ] , city_info [ city2 ] )
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28

Because it needs to be up to the connection situation of each city with surrounding cities, it needs to be connected according to the situation

``````#Build a connection If the distance between two cities is less than the threshold, it means that you can go from the current city to another city
def  build_connection ( city_info ) :
#cities_connection[key] If the key is not in the dictionary, it will return an empty list instead of reporting an error
cities_connection = defaultdict ( list ) #Get
a list of city names
cities =  list ( city_info . keys ( ) )
for c1 in cities :
for c2 in cities :
if c1 == c2 :  continue  # skip the same city

#If the distance between two cities is less than the threshold threshold, connect them
if get_city_distance ( c1 , c2 )  < threshold : #Add
the city name to the dictionary value of
cities_connection [ c1 ] . append ( c2 )
return cities_connection
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

Result test:

``````cities_connection = build_connection(city_info)
# draw connecting lines
cities_connection_graph = nx.Graph(cities_connection)
nx.draw(cities_connection_graph,city_info,with_labels=True,node_size=10)
``````
• 1
• 2
• 3
• 4

``````#sort function
def  sort_by_distance ( pathes ) :
def  get_distance_of_path ( path ) :
distance =  0
# Calculate distance sum
for i , _ in  enumerate ( path [ : - 1 ] ) :
distance += get_city_distance ( path [ i ] , path [ i ] + 1 ] )
return distance
return  sorted ( pathes , key = get_distance_of_path )

def  BFS ( graph , start , destination , search_strategy ) :

#Initial node pathes =  [ [ start ] ] #When
the queue is not empty
while paths : #The path
to take out the head of the queue
path = paths . pop ( 0 ) #Get
the last city of the path
frontiter = path [ -1 ] #Get the list of cities that the city can reach
successsors = graph [
froniter ]
#traverse the list
for city in successsors : #if
the city has been skipped between paths [equivalent to being marked]
if city in path :  continue #not
in the path, add it to the current path
new_path = path +  [ city ]
# Enqueue the current path
pathes . append ( new_path )   # bfs
# Sort the data in the result according to the sorting strategy
pathes = search_strategy ( pathes )
# If paths are not empty and the last location with the shortest distance is the target location. then returns the current path
if paths and  (destination == paths [ 0 ] [ - 1 ] ) :
return paths [ 0 ]
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35

The main function code is as follows:

``````if __name__ ==  '__main__' :
city_info = get_city_info ( coordination_source )
#print(city_info)
# draw the map
city_graph = nx . Graph ( )
city_graph . add_nodes_from ( list ( city_info . keys ( ) ) )
matplotlib . rcParams [ 'font . sans -serif' ]  =  [ 'KaiTi' ]   # Modify font
nx .draw ( city_graph , city_info , with_labels = True , node_size = 10 )

#Connect cities
cities_connection = build_connection ( city_info )
cities_connection_graph = nx . Graph ( cities_connection )
nx . draw ( cities_connection_graph , city_info , with_labels = True , node_size = 8 )
#plt.show()
print ( BFS ( cities_connection ,  "Beijing " ,  "Shanghai" , search_strategy =sort_by_distance ) )
print ( BFS ( cities_connection ,  "Zhengzhou" ,  "Shanghai" , search_strategy = sort_by_distance ) )
``````
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

The output is as follows:

``````['Beijing', 'Tianjin', 'Shanghai']
['Zhengzhou', 'Nanjing', 'Shanghai']
``````
• 1
• 2