python - Networkx,用最短路径做最短周期
问题描述
这个问题是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 做我想做的事情?
谢谢你。
解决方案
您可以尝试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))
推荐阅读
- curl - 卷曲请求 - 无法解析主机:“密码”
- c# - 'await' 运算符只能在异步 lambda 表达式中使用。考虑用 'async' 修饰符标记这个 lambda 表达式
- sql - Impala - 在 WITH 子句之后创建 TABLE
- oracle - APEX 5.1 中的经典报表动态标题
- r - 替换的行与初始行不同
- perl - 奇怪的正则表达式
- python - 屏蔽 Numpy 数组并在不使用 for 循环的情况下对每个掩码应用计算
- javascript - 图 1 在第二次调用函数时挂起
- algorithm - 在标记和清除中,在什么情况下堆栈会比分配的堆节点持有更多的指针?
- javascript - 忽略调试器;声明,但仍然在 dev-tools/IDE 中评估我自己的断点