Наименьшее расстояние между узлами (скажем, все дома) до группы узлов (скажем, больницы) с использованием 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.