networkx - How to optimize a script about computing shortest path between two points - python

Question

I have a networkx graph G that contains public transport stops stations data as nodes and the edges represent each routes of the public transport network. I have a script that returns a pair of points coordinates ([x_coord1, y_coord1] and [x_coord2, y_coord2]) a certain amount of time.

I wanted to be able to get the two closest stop stations on G for this pair of points, and then compute the shortest path between them.

I did that and it is working really well but it is taking too much time. It takes about 600-850 ms for the whole function to run (see code underneath) which is too long (as I need to be doing that on loop for approximately 10 millions paths).

Bellow is the function I wrote knowing that:

• A is an array of lists of all the lon/lat values of every nodes of G in the format array([[x1, y1], [x2, y2], [x3, y3], ...])
• coord_source in the format [x_coord1, y_coord1] is the first point of the pair returned by the previous script
• coord_targ in the format [x_coord2, y_coord2] is the second point of the pair returned by the previous script

def short_path(A, coord_source, coord_targ, G):
    get1 = A[spatial.KDTree(A).query(coord_source)[1]]  ###--- Gets the closest stop station to pt1 and %time of this line gives a walltime of 150 ms approximately
    get2 = A[spatial.KDTree(A).query(coord_targ)[1]]  ###--- same for this one but for pt2
    
    for k in G.nodes().keys():
        lon = G.nodes()[k]['stop_lon']
        lat = G.nodes()[k]['stop_lat']            

        if (lon == get1[0]) & (lat == get1[1]):
            source = k
        if (lon == get2[0]) & (lat == get2[1]):
            target = k
    
    pcc = nx.shortest_path(G, source=source, target=target, weight='time')  ###--- %time of this line gives a walltime of 200 ms

Is there a way to get my script to run faster? Also please do tell me if some parts are not clear enough and I'll do my best to explain them better.

Answer 1

等待大神答复