python - 如何优化关于计算两点之间最短路径的脚本 - python

Question

我有一个 networkx 图G，其中包含作为节点的公共交通站点数据，边表示公共交通网络的每条路线。我有一个脚本，它返回一对点坐标（[x_coord1, y_coord1]和[x_coord2, y_coord2]）一定的时间。

我希望能够G为这对点打开两个最近的停靠站，然后计算它们之间的最短路径。

我这样做了，它工作得非常好，但它花费了太多时间。整个函数运行大约需要600-850 毫秒（参见下面的代码），这太长了（因为我需要在循环中执行大约1000 万条路径）。

Bellow 是我写的函数，我知道：

• GA 是格式中每个节点的所有 lon/lat 值的列表数组array([[x1, y1], [x2, y2], [x3, y3], ...])
• 格式中的 coord_source[x_coord1, y_coord1]是前一个脚本返回的对的第一个点
• 格式中的 coord_targ[x_coord2, y_coord2]是前一个脚本返回的对的第二个点

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

有没有办法让我的脚本运行得更快？另外，如果某些部分不够清楚，请告诉我，我会尽力更好地解释它们。

标签： pythonnetworkxkdtree