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

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），但我想知道如何获得每个节点与[=13中的几个目标之间的所有最短路径=]（目标列仅用于构建目的）。

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'] 将是 Luke 和 Christopher 之间的 a 最短路径，或者如果节点之间没有路径，则将导致 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和[=13=之间没有路径的情况会快 ].我只是在懒惰编写的单行代码中调用了额外的 nx.has_path() 函数，但我将把它留作 reader 优化的练习。 ;^)

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

Shortest path between each node in the graph and elements in a list

python

networkx