基于NetworkX的有环有向图路径查找：含单次环路径实现

首先，我先明确你的核心需求：你需要找出从Start到End的所有路径，包括那些经过一次环但不会无限循环的路径——而你当前使用的networkx.all_simple_paths只能返回无重复节点的简单路径，自然会漏掉这类带单次环的路径。

先梳理下你的图里的两个环（从你提供的代码结构中提取）：

• 环1：3 → 6 → 5 → 3
• 环2：4 → 7 → 10 → 4

你提到的3条缺失路径，正是经过这两个环其中一次的路径。下面是具体的实现方案：

自定义DFS搜索函数 #

我们可以写一个深度优先搜索（DFS）的递归函数，允许路径中的节点最多出现2次（这样既允许经过一次环，又能彻底避免无限循环），具体代码如下：

import networkx as nx

# 复用你定义的图结构
Demo_Bussines_Process_Diagram = {
    "Start": ["1"], 
    "1": ["2"], 
    "2": ["3", "4"], 
    "3": ["6"], 
    "4": ["7"], 
    "5": ["3", "8"], 
    "6": ["5", "8"], 
    "7": ["10"],
    "8": ["9"],
    "9": ["End"],
    "10": ["8", "4"]
}

# 构建并冻结有向图
Business_Process = nx.MultiDiGraph(Demo_Bussines_Process_Diagram)
nx.freeze(Business_Process)

def find_paths_with_single_cycle(graph, start, end):
    paths = []
    
    def dfs(current_node, current_path, node_counts):
        # 到达终点，记录完整路径
        if current_node == end:
            paths.append(current_path.copy())
            return
        
        # 遍历当前节点的所有邻居
        for neighbor in graph.neighbors(current_node):
            # 限制每个节点最多出现2次，避免无限循环
            if node_counts.get(neighbor, 0) < 2:
                # 更新当前路径和节点计数
                current_path.append(neighbor)
                node_counts[neighbor] = node_counts.get(neighbor, 0) + 1
                
                # 递归探索下一个节点
                dfs(neighbor, current_path, node_counts)
                
                # 回溯：恢复路径和计数，不影响其他分支搜索
                current_path.pop()
                node_counts[neighbor] -= 1
                if node_counts[neighbor] == 0:
                    del node_counts[neighbor]
    
    # 初始化搜索：从Start节点开始，初始路径包含Start，计数为1
    dfs(start, [start], {start: 1})
    return paths

# 获取所有符合要求的路径
all_valid_paths = find_paths_with_single_cycle(Business_Process, "Start", "End")

# 打印结果
for idx, path in enumerate(all_valid_paths, 1):
    print(f"Path {idx} is {path}")

代码逻辑说明 #

1. 核心限制：用node_counts字典跟踪每个节点在当前路径中的出现次数，限制最多出现2次——这样既允许路径经过一次环（节点重复一次），又能阻止无限循环（节点不会重复超过2次）。
2. 回溯机制：递归后恢复路径和节点计数，确保每个搜索分支的独立性，不会互相干扰。
3. 结果覆盖：这个函数会返回所有简单路径，加上经过一次环的路径，比如：
   • Start →1→2→3→6→5→3→6→8→9→End（经过环3-6-5-3一次）
   • Start →1→2→4→7→10→4→7→10→8→9→End（经过环4-7-10-4一次）
   • Start →1→2→3→6→5→8→9→End（这条是简单路径，也会被包含）

运行这段代码后，你就能找到之前漏掉的3条带单次环的路径，同时不会出现无限循环的情况。

内容的提问来源于stack exchange，提问作者M. Morgan