graph - Python: NetworkX Finding shortest path which contains given list of nodes -

graph - Python: NetworkX Finding shortest path which contains given list of nodes -

i have graph

g=nx.graph()

and edges

g.add_edge('a', 'b') g.add_edge('a', 'e') g.add_edge('b', 'c') g.add_edge('c', 'd') g.add_edge('d', 'e') g.add_edge('e', 'g') g.add_edge('g', 'f') g.add_edge('g', 'h') g.add_edge('g', 'k') g.add_edge('h', 'j') g.add_edge('h', 'i')

and suppose want shortest path start node 'a' , should contain nodes ['d', 'k'] output should ['a', 'b', 'c', 'd', 'e', 'g', 'k'] there networkx function can give me such output?

i don't know of library function homecoming shortest paths include multiple nodes.

if not computationally expensive @ every path between start node , end node, filter list of homecoming paths include nodes looking for.

class="lang-python prettyprint-override"># lambda check if list of paths includes nodes only_containing_nodes = lambda x: 'd' in x , 'k' in x # if want find shortest path includes nodes # paths , can filtered , ordered # length. all_simple_paths = nx.all_simple_paths(g, source='a', target='k') # if want shortest paths include both nodes if # path includes nodes , not shortest. all_shortest_paths = nx.all_shortest_paths(g, source='a', target='k') filter(only_containing_nodes, all_simple_paths) # >>> [['a', 'b', 'c', 'd', 'e', 'g', 'k']] filter(only_containing_nodes, all_shortest_paths) # >>> []

i hope helps.

python graph networkx