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
    radius =  6371   # km

    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 ) ) 
    d= radius * c

    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 )

#Breadth-first search BFS 
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