图中每个节点与列表中元素之间的最短路径 [英] 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()函数，但我将把它作为练习留给读者进行优化。；^)

这篇关于图中每个节点与列表中元素之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！