如何利用NetworkX最短路径工具求解无向图指定节点的最短环？

嘿，我懂你不想自己写复杂的遍历函数，想靠NetworkX自带的工具搞定指定节点k的最短简单环需求——刚好有个巧妙的思路，完全用NetworkX的Shortest系列工具就能实现，不用从头造轮子！

节点k的最短简单环（起点终点都是k，中间节点不重复），本质上就是找k的某个邻居v，然后找到v到k的不直接走k-v边的最短简单路径，把k→v和这条路径拼接起来就形成了环，最后在所有可能的环里挑最短的那个就行。

假设你的无向无权图已经用G表示，目标节点是k，直接用下面的代码就行：

import networkx as nx

# 先做基础校验
if k not in G.nodes():
    raise ValueError("节点k不在当前图里哦")
neighbors = list(G.neighbors(k))
if not neighbors:
    print("节点k连邻居都没有，根本不存在环呀")

min_cycle_length = float('inf')
min_cycle = None

# 遍历k的每个邻居，计算可能的最短环
for v in neighbors:
    # 临时移除k-v这条边，避免直接走回k形成无意义的2节点环
    G.remove_edge(k, v)
    try:
        # 用NetworkX的最短路径工具找v到k的最短路径（无权图里最短路径必然是简单路径）
        path = nx.shortest_path(G, source=v, target=k)
        # 拼接成完整的环：k -> v -> ... -> k
        cycle = [k] + path
        current_length = len(cycle)
        # 更新最短环
        if current_length < min_cycle_length:
            min_cycle_length = current_length
            min_cycle = cycle
    except nx.NetworkXNoPath:
        # 移除k-v边后v到k没路径，说明这条边不在任何简单环里，直接跳过
        pass
    finally:
        # 不管成功失败，都把移除的边加回去，别破坏原图
        G.add_edge(k, v)

# 输出结果
if min_cycle:
    print(f"节点{k}的最短简单环是: {min_cycle}，环长为{min_cycle_length}")
else:
    print(f"节点{k}所在的图里没有简单环哦")

• 无向无权图中，nx.shortest_path返回的绝对是简单路径——毕竟最短路径不可能带环，不然去掉环路径会更短，矛盾嘛。
• 临时移除k-v边，确保我们找到的路径不会直接从v跳回k，这样形成的环至少有3个节点，完全符合你要的“仅经过每个节点一次（除了起点终点k）”的要求。
• 遍历所有邻居后取最小的环长，自然就能得到k的最短简单环。

小提醒 #

• 如果你的图是多重图（允许两个节点之间有多条边），那得稍微调整逻辑——比如移除所有k-v边再计算，不过一般简单图的场景下上面的代码足够用。
• 如果k不在任何环里（比如是树里的节点），那代码会提示没有简单环，这也符合实际情况。

内容的提问来源于stack exchange，提问作者Travis Black