Networkx: Get the distance between nodes

Question

I'm a beginner at using NetworkX and I'm trying to find a way to detect which nodes have distance x from each other. I've started by using this algorithm to get all pairs

path=nx.all_pairs_dijkstra_path(G)

But I'm still unsure on how to detect the distance between nodes using a for loop.

I'd appreciate any help. Thank you

Answer 1

NetworkX has methods for automatically calculating the shortest paths (or just the path lengths) for weighted and unweighted graphs. Make sure that you use the correct method for your use case.

networkx.all_pairs_shortest_path - calculates the shortest paths between all nodes in an unweighted graph

networkx.all_pairs_shortest_path_length - calculates the lengths of the shortest paths between all nodes in an unweighted graph

networkx.all_pairs_dijkstra_path - calculates the shortest paths between all nodes in a weighted graph

networkx.all_pairs_dijkstra_path_length - calculates the lengths of the shortest paths between all nodes in a weighted graph

Every one of these methods, when executed on a graph, will calculate a dictionary matrix (a "dictionary of dictionaries") of nodes with either the respective shortest path or length of the shortest path as values. I'll demonstrate this with an example:

>>> 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 = dict(nx.all_pairs_shortest_path(G))
>>> sp["A"]["E"]
['A', 'B', 'C', 'D', 'E']
>>> spl = dict(nx.all_pairs_shortest_path_length(G))
>>> spl["A"]["E"]
4

As you can see, I generated a graph with five nodes and linked every node to the next one with an edge. I stored a matrix of the shortest paths in sp and a matrix of the shortest path lengths in spl. When I need to know the shortest path between two nodes, e.g. node "A" and node "E", I just access sp like a matrix, or a dictionary of dictionaries: sp["A"]["E"]. It will then return the whole shortest path between the two nodes. The method for the shortest path length works in a similar fashion, but it will return only the number of edges between any two given nodes.

The next code snippet might make it clearer what I mean with a dictionary matrix. If I request all entries in sp for node "A", it returns another dictionary with entries for every other node:

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

If you want to check out the distance between all nodes by using for loops, you could just iterate over the keys of the first dictionary of the matrix and then over the dictionaries inside of that dictionary. It's easier than it sounds:

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