Networkx: Holen Sie sich die Entfernung zwischen den Knoten

NetworkX hat Methoden für die automatische Berechnung der kürzesten Pfade (oder nur den Pfad-Längen) für die gewichteten und ungewichteten Graphen. Stellen Sie sicher, dass Sie verwenden die richtige Methode für Ihren Fall.

networkx.all_pairs_shortest_path - berechnet die kürzesten Pfade zwischen allen Knoten in einem ungewichtet graph

networkx.all_pairs_shortest_path_length - berechnet die Längen der kürzesten Wege zwischen allen Knoten in einem ungewichtet graph

networkx.all_pairs_dijkstra_path - berechnet die kürzesten Pfade zwischen allen Knoten in einem gewichtet graph

networkx.all_pairs_dijkstra_path_length - berechnet die Längen der kürzesten Wege zwischen allen Knoten in einem gewichtet graph

Jeder von diesen Methoden werden auch ausgeführt, wenn Sie auf ein Diagramm, berechnen, ein Wörterbuch-matrix (ein "Wörterbuch der Wörterbücher") von Knoten mit entweder der jeweils kürzeste Pfad oder die Länge des kürzesten Weges als Werte. Ich werde Ihnen an einem Beispiel zeigen:

>>> 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

Wie Sie sehen können, erzeugt einen Graphen mit fünf Knoten und verknüpft mit jedem Knoten der nächsten mit einer Kante. Ich habe gespeichert eine matrix der kürzesten Wege in sp und eine matrix der kürzesten Pfadlängen in spl. Wenn ich wissen muss, um den kürzesten Pfad zwischen zwei Knoten, z.B. den Knoten "A" und Knoten "E" ich einfach Zugriff sp wie eine matrix, oder ein dictionary von dictionaries: sp["A"]["E"]. Es wird dann wieder die ganze kürzesten Pfad zwischen den beiden Knoten. Die Methode für den kürzesten Pfad der Länge arbeitet in einer ähnlichen Weise, aber es wird wieder nur die Anzahl der Kanten zwischen zwei bestimmten Knoten.

Nächsten Codeausschnitt könnte es klarer, was ich meine, mit einem Wörterbuch-matrix. Wenn ich alle Einträge in sp für Knoten "A" ist, gibt es ein weiteres Wörterbuch mit Einträgen für alle anderen Knoten:

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

Wenn Sie möchten, heraus zu überprüfen den Abstand zwischen allen Knoten mithilfe for Schleifen, könnte man nur die Iteration über die Schlüssel des ersten Wörterbuch der matrix und dann über die Wörterbücher, die im inneren des Wörterbuchs. Es ist einfacher als es klingt:

>>> 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!)

Bitte lassen Sie mich wissen, wenn Sie irgendwelche Fragen haben.