基于NetworkX的网络链路路径查找：允重复节点禁重复边的实现问询

好问题！你需要的是允许重复节点但禁止重复边的路径（这类路径也常被称为“边简单路径”），NetworkX确实没有直接提供现成的API，但我们可以基于它的图结构，用深度优先搜索（DFS）实现一个高效的遍历算法，不用像之前那样先搜所有路径再过滤，能大幅提升效率。

为什么nx.all_simple_paths不适用？ #

nx.all_simple_paths的核心限制是节点不可重复，这和你的需求冲突——你需要节点可以重复，但每条边只能走一次。直接用它的话会漏掉很多符合要求的路径，后续过滤的方式不仅麻烦，还会浪费大量计算资源在生成无效路径上。

高效实现思路：跟踪已使用的边 #

我们可以自己实现DFS遍历，重点是记录已经走过的边，而不是节点。因为是无向图，同一条边的两个方向（比如A→C和C→A）其实是同一条，所以用frozenset({u, v})来唯一标识每条边，避免重复计数。

完整代码实现 #

import networkx as nx

def find_edge_simple_paths(g, source, target):
    """查找从source到target的所有无重复边路径，返回每条路径对应的edge sku列表"""
    paths = []
    
    def dfs(current_node, used_edges, current_path):
        # 到达目标节点，记录当前路径
        if current_node == target:
            paths.append(current_path.copy())
            return
        
        # 遍历当前节点的所有邻接边
        for neighbor, edge_attrs in g[current_node].items():
            edge_sku = edge_attrs["sku"]
            # 用frozenset唯一标识无向边（避免A→C和C→A被当成两条不同边）
            edge_key = frozenset({current_node, neighbor})
            
            if edge_key not in used_edges:
                # 标记这条边已使用
                used_edges.add(edge_key)
                current_path.append(edge_sku)
                # 递归访问邻居节点
                dfs(neighbor, used_edges, current_path)
                # 回溯：取消边的标记，移除路径中的当前sku
                used_edges.remove(edge_key)
                current_path.pop()
    
    # 启动DFS：从source出发，初始无已使用边，路径为空
    dfs(source, set(), [])
    return paths

测试你的示例场景 #

用你提到的图结构测试：

# 构建你的图
g = nx.Graph()
g.add_edges_from([
    ("A", "B", {"sku": "Edge1"}),
    ("B", "C", {"sku": "Edge2"}),
    ("A", "C", {"sku": "Edge3"}),
    ("C", "D", {"sku": "Edge4"}),
    ("B", "E", {"sku": "Edge5"}),
    ("D", "E", {"sku": "Edge6"}),
    ("C", "E", {"sku": "Edge7"})
])

# 查找A到D的所有无重复边路径
result = find_edge_simple_paths(g, "A", "D")
# 打印你提到的那条路径
for path in result:
    if path == ["Edge3", "Edge7", "Edge5", "Edge2", "Edge4"]:
        print("找到目标路径：", path)

运行后就能找到你需要的那条路径，同时还会返回其他所有符合规则的路径。

效率优势 #

这个算法是按需遍历，只会生成符合“无重复边”规则的路径，不会像你之前的方法那样生成大量冗余路径再过滤。对于边数较多的图，效率提升会非常明显。另外，因为每条边只能用一次，所以路径的最大长度就是图的总边数，不会出现无限循环的问题。

内容的提问来源于stack exchange，提问作者Achraf Bentabib