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

Question

下面的数据帧

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

用于构建网络（其中节点是源节点）：

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

我想列出源节点和单独列表中的节点之间的所有最短路径（如果存在）：

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

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

Answer 1

做到这一点的最简单方法是，只要您的网络很小，就没有指定source或target参数时，使用默认行为nx.shortest_path(G)。如果您只是运行all_shortest = nx.shortest_path(G)，则根据docs：

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

然后all_shortest['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()函数，但我将把它作为练习留给读者进行优化