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

Shortest path between each node in the graph and elements in a list(图中每个节点与列表中元素之间的最短路径)

问题描述

以下数据帧

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']

有几种方法可以计算网络x中的最短路径(例如，SHORTEST_PATH)，但我想知道如何才能获得每个节点与list4pth中的几个目标之间的所有最短路径(Target列仅用于构建目的)。

推荐答案

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

如果既未指定源也未指定目标，则返回路径为[源][目标]=[路径中的节点列表]的词典。

则all_shortest['Luke']['Christopher']将是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之间没有路径的情况，速度会快得多。我只是在一个懒惰地编写的一行程序中调用了Extranx.has_path()函数，但我将把它作为练习留给读者进行优化。；^)