python - networkx 中的编码求和 i > j

Question

我正在使用networkx（和gurobi）来计算一组节点中节点之间的最短路径。但是我需要以特定方式计算所有最短路径的总和，即，

对所有 i > j 的 dij 求和

其中 dij 是节点 i 和 j 之间的最短路径

grb.quicksum(nx.shortest_path_length for i > j in g.edges)

我认为这是非常错误的。

Answer 1

目前尚不清楚您为什么同时使用 gurobi 和 nx.short_path_length。networkx 的 shortest_path_length() 和 python 的 sum() 就是你所需要的：

import itertools as it
import networkx as nx
...
G = nx.Graph()
...
# Define edges of G ...
...
sum(nx.shortest_path_length(G,i,j) for (i,j) in it.combinations(G.nodes(),2))

这假设图 G 的任意两个节点之间都有一条路径。如果没有，我们会得到类似的结果：

NetworkXNoPath: No path between 1 and 7.

gurobi 的 quicksum() 用于汇总 gurobi 变量，然后将其作为约束或目标函数传递给 gurobi 模型。