NetworkX has methods for automatically calculating shortest paths (or just path lengths) for weighted and unweighted graphs. Make sure 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
Each of these methods, performed on a graph, will compute a dictionary matrix (“dictionary of dictionaries”) of nodes having either the shortest path or the length of the shortest path as values. I will 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 = 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
As you can see, I generated a graph with five nodes and linked each node to the next with an edge. I saved the shortest path matrix in sp and the shortest path matrix in spl . When I need to know the shortest path between two nodes, for example. node "A" and node "E" , I just get access to sp as a matrix or dictionary of dictionaries: sp["A"]["E"] . Then it will return the entire shortest path between the two nodes. The shortest path method works the same way, but it will only return the number of edges between any two given nodes.
The following code snippet can make it clearer what I mean with the vocabulary matrix. If I request all the entries in sp for node "A" , it returns another dictionary with entries for all the 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 the distance between all nodes using for loops, you can simply iterate over the keys of the first matrix dictionary, and then over the dictionaries inside this dictionary. This is 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!)
Please let me know if you have any questions.