时间戳

首页 > 解决方案 > 为网络中的每一对找到最短路径

python - 为网络中的每一对找到最短路径

问题描述

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

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

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

标签： pythonpandascsvnetworkxgraph-theory

解决方案

您可以使用 networkx 来实现这一点，特别是nx.shortest_path. 此算法查找源节点和目标节点之间的最短路径，或者如果未指定，则生成每个节点对（存在路径的位置）之间的所有最短路径的字典。

对于您的示例：

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

推荐阅读