使用python为网络中的每一对查找每一条可能的短路径

Question

我有一个csv文件中从父级到子级的定向边列表，如下所示：

    parent  child
0   7       4847454
1   7       14823924
2   7       31208539
3   7       32584634
4   7       54293428

我想找出网络中每一对可能的节点之间的最短路径。我该怎么做？我不确定在这种情况下哪个软件包是最好的（networkX、igraph等）

Answer 1

您可以使用networkx实现这一点，特别是^{}。此算法查找源节点和目标节点之间的最短路径，如果未指定最短路径，则生成每个节点对（存在路径）之间所有最短路径的字典。你知道吗

举个例子：

>>> df = pd.DataFrame({'parent': {0: 7, 1: 7, 2: 7, 3: 7, 4: 7},
                   'child': {0: 4847454, 1: 14823924, 2: 31208539, 3: 32584634, 4: 54293428}})
>>> G = nx.convert_matrix.from_pandas_edgelist(df, 'parent', 'child', create_using=nx.DiGraph)
>>> nx.shortest_path(G)
{7: {7: [7],
     4847454: [7, 4847454],
     14823924: [7, 14823924],
     31208539: [7, 31208539],
     32584634: [7, 32584634],
     54293428: [7, 54293428]},
 4847454: {4847454: [4847454]},
 14823924: {14823924: [14823924]},
 31208539: {31208539: [31208539]},
 32584634: {32584634: [32584634]},
 54293428: {54293428: [54293428]}}