源和目标网络列表的最短路径 x

Question

我有一个具有如下相关节点和边的图：

我想要的是找到一种方法来仅对列表中包含的节点执行 shortest_path networkx，即：

source = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destination = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

我不想手工做这个，即：

nx.shortest_path(G, source="10.0.11.100", target="10.0.12.100")
nx.shortest_path(G, source="10.0.11.100", target="10.0.13.100")
nx.shortest_path(G, source="10.0.11.100", target="10.0.14.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.11.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.13.100")
nx.shortest_path(G, source="10.0.12.100", target="10.0.14.100")
...

我想要的结果如下所示：

[('10.0.12.100','10.0.14.100',['10.0.1.11', '10.0.1.23']), ('10.0.14.100', '10.0.12.100', ['10.0.1.22', '10.0.1.9']), ('10.0.11.100', '10.0.14.100', ['10.0.1.6', '10.0.1.18', '10.0.1.26']), ('10.0.14.100', '10.0.11.100' ,['10.0.1.25', '10.0.1.17', '10.0.1.5'])...]

即[(Source, Destination, [Path from Source to Destination])]

有什么办法吗？非常感谢

这是我的代码：

import networkx
G = nx.DiGraph()
z = [('10.0.12.100', '10.0.1.1'),('10.0.1.1', '10.0.11.100'),('10.0.11.100', '10.0.1.2'),('10.0.1.2', '10.0.12.100'),('10.0.13.100', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.11.100'),('10.0.11.100', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.13.100'),('10.0.11.100', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.1.26'),('10.0.1.26', '10.0.14.100'),('10.0.14.100', '10.0.1.22'),('10.0.1.22', '10.0.1.9'),('10.0.1.9', '10.0.12.100'),('10.0.12.100', '10.0.1.1'),('10.0.1.1', '10.0.1.6'),('10.0.1.6', '10.0.1.18'),('10.0.1.18', '10.0.13.100'),('10.0.13.100', '10.0.1.26'),('10.0.1.26', '10.0.14.100'),('10.0.13.100', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.1.2'),('10.0.1.2', '10.0.12.100'),('10.0.14.100', '10.0.1.25'),('10.0.1.25', '10.0.1.17'),('10.0.1.17', '10.0.1.5'),('10.0.1.5', '10.0.11.100'),('10.0.12.100', '10.0.1.11'),('10.0.1.11', '10.0.1.23'),('10.0.1.23', '10.0.14.100'),('10.0.14.100', '10.0.1.25'),('10.0.1.25', '10.0.13.100')]
G.add_edges_from(z)
random_pos = nx.random_layout(G, seed=42)
pos=nx.spring_layout(G, pos=random_pos) 
nx.draw(
    G,
    pos=pos,
    node_color='#FF0000',
    with_labels=True,
    arrows=False
)

source = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destination = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

list_shortest_path = []
for i in G.nodes(data=True):
  DD = list_shortest_path.append(nx.shortest_path(G, source=i[0], target=i[1]))

Answer 1

这不是源节点的组合吗？

from itertools import combinations

for n1, n2 in combinations(source, 2):
    list_shortest_path.append((n1, n2, nx.shortest_path(G, source=n1, target=n2))

Answer 2

简单地说，你可以做一个双 for 循环：

sources = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]
destinations = ["10.0.11.100","10.0.12.100","10.0.13.100","10.0.14.100"]

res = []
for s in sources:
    for d in destinations:
        res.append((s, d, nx.shortest_path(G, source=s, target=d)))

但这对于某些图表可能会有一些问题：

在 DiGraph（你的情况）的情况下，这应该是解决方案，因为它考虑了两端的最短路径（源到目标与目标到源的路径不同)。
如果您要使用 Graph（没有有向边），最有效的解决方案看起来类似于@Vanojx1 的答案。

Answer 3

您可以使用 itertools.product 和列表理解。

from itertools import product

list_shortest_path = [(src, dst, nx.shortest_path(G, source=src, target=dst) 
for src, dst in product(sources, destinations) if src != dst]

源和目标网络列表的最短路径 x

Shortest path of a list of Source and Destination networkx

python

graph

list

networkx

python-3.x