CODEWITHSUNDEEP
networkxgraph-theoryshortest-path
Xia
Xia

Reputation: 166

Finding all shortest paths between two nodes in NetworkX

Assume I have a BA network with N nodes where each node has at least 2 edges. The network is unweighted. I am trying to find all the shortest paths between every node i and j for all nodes in the network. But if there are more than 1 shortest path between node i and j, then I need every single shortest path between i and j.

So if node 2 can be reached from 0 by using the paths [0,1,2], [0,3,4,2], [0,3,4,5,2], [0,4,5,2] and [0,3,2], I need a list that says [[0,1,2], [0,3,2]].

Is the only way of doing this is calculating each path from i to j and getting the smallest lenghted lists? Can this be founded in a more efficient way?

Edit: Apparently there's a path finding method called all_shortest_paths. I will try this and see if it is efficient.

Upvotes: 1

Views: 2394

Answers (2)

yatu
yatu

Reputation: 88305

You can use nx.nx.all_shortest_paths for this:

all_shortest_paths(G, source, target, weight=None, method='dijkstra')

Which allows you to specify a source and target nodes. Here's a simple example:

plt.figure(figsize=(6,4))
G = nx.from_edgelist([[1,2],[2,3],[7,8],[3,8],[1,8], [2,9],[9,0],[0,7]])
nx.draw(G, with_labels=True, node_color='lightgreen')

enter image description here

list(nx.all_shortest_paths(G, 2, 8))
# [[2, 1, 8], [2, 3, 8]]

Upvotes: 2

Andrey
Andrey

Reputation: 2078

Floyd Warshall algorithm is that what you need

Upvotes: 0

Related Questions