在 networkx 中编码求和 i > j

Question

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

dij 的所有 i > j 的总和

其中 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 变量求和，然后将其作为约束或 objective 函数传递到 gurobi 模型中。

在 networkx 中编码求和 i > j

Coding summation i > j in networkx

python

gurobi