Networkx: получить расстояние между узлами

Question

Я новичок в использовании NetworkX, и я пытаюсь найти способ определить, какие узлы имеют расстояние x друг от друга. Я начал с помощью этого алгоритма, чтобы получить все пары

path=nx.all_pairs_dijkstra_path(G) 

Но я все еще не уверен в том, как для определения расстояния между узлами, используя для цикла.

Буду признателен за любую помощь. Спасибо

Answer 1

В NetworkX есть методы для автоматического вычисления кратчайших путей (или только длины пути) для взвешенных и невзвешенных графиков. Убедитесь, что вы используете правильный метод для вашего случая использования.

networkx.all_pairs_shortest_path - вычисляет кратчайшие пути между всеми узлами в невзвешенного графа

networkx.all_pairs_shortest_path_length - вычисляет длины кратчайших путей между всеми узлами в невзвешенного графа

networkx.all_pairs_dijkstra_path - вычисляет самое короткие пути между всеми узлами в взвешенные график

- вычисляет длины кратчайших путей между всеми узлами в взвешенного графа

Каждые из этих методов, которые при выполнении на графике, будет вычислять словарь матрицы («словарь словарей») узлы с либо самый короткий путь или длина кратчайшего пути в качестве значений. Я продемонстрирую это на примере:

>>> import networkx as nx 
>>> G = nx.Graph() 
>>> G.add_nodes_from(["A", "B", "C", "D", "E"]) 
>>> G.add_edges_from([("A", "B"), ("B", "C"), ("C", "D"), ("D", "E")]) 
>>> sp = nx.all_pairs_shortest_path(G) 
>>> sp["A"]["E"] 
['A', 'B', 'C', 'D', 'E'] 
>>> spl = nx.all_pairs_shortest_path_length(G) 
>>> spl["A"]["E"] 
4 

Как вы можете видеть, я создал граф с пятью узлами и связан каждый узел к следующему с краем. Я сохранил матрицу кратчайших путей в sp и матрицу кратчайших длин пути в spl. Когда мне нужно знать кратчайший путь между двумя узлами, например. узел "A" и узел "E", я просто обращаюсь к sp как матрица или словарь словарей: sp["A"]["E"]. Затем он вернет весь кратчайший путь между двумя узлами. Метод для кратчайшего пути работает аналогичным образом, но он будет возвращать только количество ребер между любыми двумя заданными узлами.

Следующий фрагмент кода может сделать его более понятным, что я имею в виду со словарной матрицей. Если я прошу все записи в sp для узла "A", он возвращает другой словарь с записями для каждого другого узла:

>>> sp["A"] 
{'B': ['A', 'B'], 'A': ['A'], 'E': ['A', 'B', 'C', 'D', 'E'], 'C': ['A', 'B', 'C 
'], 'D': ['A', 'B', 'C', 'D']} 

Если вы хотите, чтобы проверить расстояние между всеми узлами с помощью for петли, вы могли бы просто итерации по ключи первого словаря матрицы, а затем над словарями внутри этого словаря. Это проще, чем кажется:

>>> for node1 in spl: 
... for node2 in spl[node1]: 
...  print("Length between", node1, "and", node2, "is", spl[node1][node2]) 
... 
Length between B and B is 0 
Length between B and A is 1 
Length between B and E is 3 
Length between B and C is 1 
Length between B and D is 2 
Length between A and B is 1 
... (and so on!) 

Пожалуйста, дайте мне знать, если у вас есть вопросы.