Shortest path between each node in the graph and elements in a list

user_14695007 0
Viewed 110

The following dataframe

Node       Target
Jennifer   Maria
Luke       Mark
Johnny     Martin
Ludo       Martin
Maria      nan
Mark       Luke
Mark       Christopher

is used for building a network (where node is the source node):

G = nx.from_pandas_edgelist(edges, source='Node', target='Target')

I would like to list all the shortest path (if they exist) between the source node and nodes that are in a separate list:

list4path=['Christopher', 'Donna', 'Julian','Martin']

There are several options for calculating the shortest path in networkx (e.g., shortest_path), but I am wondering how I can get all the shortest path between each node and the several targets in the list4pth (the Target column needs only for building purpose).

networkx python
1 Answers

The simplest way to do this is to use the default behavior of nx.shortest_path(G) when no source or target arguments are specified as long as your network is small-ish. If you just run all_shortest = nx.shortest_path(G), per the docs:

If neither the source nor target are specified return a dictionary of dictionaries with path[source][target]=[list of nodes in path].

Then all_shortest['Luke']['Christopher'] will be a shortest path between Luke and Christopher or will result in a KeyError if there is no path between the nodes. Or you could use .get() to avoid the KeyError.

If your network is large enough that it's more practical to only calculate paths with targets in list4path, then you could do something like this:

selected_shortest = {source: {target: nx.shortest_path(G, source, target) for target in list4path if nx.has_path(G, source, target)} for source in G.nodes()}

which would give you the same data structure but only calculate the desired shortest paths ending in a node from list4path.

I'm sure it would be much faster to write a simple function that just handles the case where there is no path between source and target. I just called the extra nx.has_path() function in a lazily written one-liner, but I'll leave that as an exercise for the reader to optimize. ;^)

user_155344410
Related