使用 NetworkX 的节点（比如所有家庭）到一组节点（比如医院）之间的最短距离

Question

网络节点=住宅单位、医院

网络边 = 权重等于长度的道路

如何计算每个住宅区到附近医院的最短距离？

我使用了"nx.all_pairs_dijkstra_path_length"，然后为每个住宅节点过滤了到医院节点的最短路径。有没有更快更好的方法？

Answer 1

我假设你的边缘都是双向的。如果不是，请看我修改后的算法在底部反转图形。

添加一个连接到边权重为 1 的所有医院的单个节点。找到从所有节点到添加节点的最短路径。这些路径中的倒数第二个节点是医院，从住宅区到医院的最短路径是在最后一个节点截断的到此添加节点的路径。

G.add_node('auxiliary_node')
for hospital in hospitals:
    G.add_edge(hospital, 'auxiliary_node', weight=1)

paths = nx.single_source_dijkstra_path(G,'auxiliary_node', weight='weight')
for path in paths:
    if path[-1] is a residential node:
        path.pop(0) #remove the first node, 'auxiliary_node'
        #the remaining path is the shortest path from a hospital to
        #path[-1].

        #code here to reverse the path so it's a path from the
        #residential block to its nearest hospital.  And 
        #to process the path however you want.

    else:
        #it is a hospital.  Ignore it.

如果权重不对称，则反转图形。

H = G.reverse(copy=False)  #without copy=False it would make a new copy of
                           #the graph.  No need for that.
#same commands with H.

使用 NetworkX 的节点（比如所有家庭）到一组节点（比如医院）之间的最短距离

Shortest distance between nodes (say all homes) to a group of nodes (say hospitals) using NetworkX

shortest-path

networkx