Networkx，使用最短路径进行最短周期

Question

这个问题是特定于NetworkX的。 我可以制作自己的功能来完成我需要的所有事情，但这需要更长的时间，所以我想避免它。

情况：

我有一个未加权图，由 NetworkX 无向图表示。 从这个图中，我寻找"最短的周期" - 也就是说，对于给定的节点k，我找到了最短的简单路径(只通过一个节点一次(，它离开k然后回到k。

为此，我想使用任何 NetworkX 最短路径算法，并从节点 k 到节点 k 进行搜索。 问题是，似乎每个最短路径算法都只是简单地返回节点 k 作为路径。 所以，它永远不会真正离开。 而且，我不知道如何改变这一点。

一个可能的解决方案是让我做：

for each edge from k
disconnect that edge
do shortest path from the other side of that edge to k
reconnect that edge

然而，我计划做这种"最短周期"技术的次数非常大，我宁愿不必这样做。 那么，有没有更简单的方法可以使用 NetworkX 做我想做的事情？

谢谢。

Answer 1

您可以尝试cycle_basis，它尝试找到一组构成基础的循环并选择最小循环：

import networkx as nx
g = nx.Graph()
g.add_nodes_from([1,2,3,4,5,6,7])
g.add_edges_from([(1,2), (1,3), (2,4), (2,7), (3,5), (6,7), (5,6), (1,5), (3,4)])
min(nx.cycle_basis(g, 1), key=lambda cycle: len(cycle))