NetworkX中获取MultiDiGraph最短路径边权重列表的方法咨询

问题解答 #

NetworkX 暂未提供直接返回最短路径对应边列表的顶层内置函数，但可通过内置工具函数快速实现你的需求，无需编写复杂逻辑。 #

实现代码 #

你已经通过nx.shortest_path拿到了节点路径，直接通过以下步骤提取权重并计算乘积即可：

import networkx as nx
from functools import reduce
import operator

# 你已有的获取最短路径节点列表的代码
node_path = nx.shortest_path(G, source=A, target=Z, weight="factor")

factor_list = []
# 遍历路径的相邻节点对（即路径上的每条边）
for u, v in nx.utils.pairwise(node_path):
    # MultiDiGraph 中u到v可能有多条边，取factor最小的边（和shortest_path选择逻辑一致）
    edge_attrs = min(G.get_edge_data(u, v).values(), key=lambda x: x["factor"])
    factor_list.append(edge_attrs["factor"])

# 计算所有权重的乘积
factor_product = reduce(operator.mul, factor_list, 1)

注意事项 #

如果你使用的是NetworkX 2.4以下版本，没有内置的nx.utils.pairwise，可以用Python原生的zip(node_path[:-1], node_path[1:])替代，效果完全一致。

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