基于igraph v0.9.11的大规模加权图最短路径高效计算问询

我需要在一个包含160K节点、1500万条边的大规模加权无向图中，完成以下计算：

• 对每一条边，以这条边的length_difference权重为阈值，删除图中所有权重≥该阈值的边
• 计算原边两个端点在剩余子图中的最短路径边数；若无法找到路径，则将最短路径边数记为1（即保留原边的连接）

希望基于igraph v0.9.11完成，核心是在GraphBase.shortest_paths()的基础上，增加忽略权重超过指定阈值的边的功能，避免自行实现路径算法（推测igraph底层用非Python语言实现，性能更优）。理想的调用方式如下：

g = ig.Graph.TupleList(data_all.itertuples(index=False), 
                       directed=False,
                       edge_attrs=['percent', 'length_difference'] 
                       )
shortest_paths = []
for edge in g.es:
    threshold_weight = edge.attributes()['length_difference']
    shortest = g.my_pretend_shortest_paths(
        source=edge.source, 
        target=edge.target, 
        weights='length_difference', 
        mode='all', 
        ignore_weights_over=threshold_weight
    )  # 不能修改原图对象
    if not shortest:
        shortest_paths.append((edge.source, edge.target, threshold_weight, 1)) 
    else:
        shortest_paths.append((edge.source, edge.target, threshold_weight, len(shortest)))

我当前的解决方案是每次为单条边创建子图再计算路径，效率极低：

• 在含约250K边的测试图中处理500条边需600-700秒，推算处理1500万条边需约230天
• 优化后处理1-2000条边仍需约1分钟，推算全量任务需约1周
• 目标是12小时内完成全部计算

优化后的代码如下：

def ec_list_to_g(es):
    edges_formatted = []
    for e in es:
        att = e.attributes()
        edges_formatted.append((e.source, e.target, att['percent'], att['length_difference']))
    return ig.Graph.TupleList(edges_formatted, 
                directed=False,
                edge_attrs=['percent', 'length_difference'] 
                )


g = ig.Graph.TupleList(df.itertuples(index=False), 
                       directed=False,
                       edge_attrs=['percent', 'length_difference'] 
                       )
shortest_paths = []
for edge in g.es:
    threshold_weight = edge.attributes()['length_difference']
    if threshold_weight <= 1:
        continue
    target_es = g.es.select(length_difference_lt=threshold_weight)
    sub_g = ec_list_to_g(target_es)
    shortest = sub_g.shortest_paths(
        source=edge.source, 
        target=edge.target, 
        weights='length_difference', 
        mode='all'
    )
    # 后续逻辑同理想方案

内容的提问来源于stack exchange，提问作者Tim Kirkwood