图中每个节点到列表元素之间的最短路径

Question

以下数据框

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

用于构建网络(其中node是源节点):

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

我想列出源节点和在单独列表中的节点之间的所有最短路径(如果它们存在):

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

有几个选项用于计算networkx中的最短路径(例如，shortest_path)，但我想知道如何获得list4pth中每个节点和几个目标之间的所有最短路径(目标列仅用于构建目的)。

Answer 1

最简单的方法是在没有指定source或target参数时使用nx.shortest_path(G)的默认行为，只要您的网络较小。如果你只是运行all_shortest = nx.shortest_path(G)，根据docs:

如果源和目标都没有指定，返回一个由路径为[source][target]=[list of nodes in path]的字典组成的字典。

则all_shortest['Luke']['Christopher']将为a如果节点之间没有路径，Luke和Christopher之间的最短路径将导致KeyError。或者您可以使用.get()来避免使用KeyError。

如果你的网络足够大，只计算list4path中目标的路径更实用，那么你可以这样做:

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()}

，这将给你相同的数据结构，但只计算所需的最短路径结束于list4path的一个节点。

我相信这将是多写一个简单的函数，只是处理source和target之间没有路径的情况下更快。我只是在一个懒惰编写的一行代码中调用了额外的nx.has_path()函数，但我将把它作为练习留给读者去优化。, ^)