NetworkX 简单路径算法全指南all_simple_paths、shortest_simple_paths 与源码级原理剖析【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkx简单路径Simple Path是图论中最基础也最重要的概念之一一条不重复经过任何节点的路径。在 NetworkX 中simple_paths 模块 集中提供了四个核心 API——all_simple_paths、all_simple_edge_paths、is_simple_path与shortest_simple_paths覆盖了枚举全部简单路径、按最短到最长排序输出与路径合法性校验三大场景。本文将以 doc/reference/algorithms/simple_paths.rst 中列出的四个公开接口为主线结合源码实现与测试用例深入讲解每个函数的用法、参数语义、边界行为与底层算法原理帮助你在大规模图上正确、高效地使用 NetworkX 的简单路径能力。什么是简单路径模块的语义基础在 simple_paths.py 的is_simple_path文档中给出了精确定义图中的简单路径是一个非空的节点序列序列中每个节点最多出现一次且序列中每一对相邻节点在图中有边相连。需要特别留意两个约定路径长度以边数计长度为n的节点列表对应长度为n- 1 的路径即边数。因此最小的边路径是零条边的空路径它对应只有一个节点的列表。这就是为什么is_simple_path(G, [node])被认为是合法路径而is_simple_path(G, [])不是。节点路径与边路径存在一一对应节点路径[0, 1, 2, 3]与边路径[(0, 1), (1, 2), (2, 3)]可以互相转换转换工具是networkx.utils.pairwise实现于 utils/misc.py。 from networkx.utils import pairwise nodes [0, 1, 2, 3] edges list(pairwise(nodes)) edges [(0, 1), (1, 2), (2, 3)] nodes [edges[0][0]] [v for u, v in edges] nodes [0, 1, 2, 3]整个模块的四个函数正是围绕这一语义展开前两个枚举节点/边视角的全部简单路径第三个做合法性校验第四个按长度排序输出。is_simple_path验证一个节点序列是否构成简单路径is_simple_path(G, nodes)接收一个图和一个节点列表返回布尔值。它是模块中最轻量、也最适合做前置校验的函数。判断规则与实现细节从源码simple_paths.py可以看到它按顺序执行五层检查空列表直接返回False空列表不是路径但单节点列表是路径单节点列表只需确认该节点确实存在于图中列表中只要有任意节点不在图中返回False列表中出现重复节点len(set(nodes)) ! len(nodes)说明节点被重复经过不是简单路径返回False逐对检查相邻节点是否有边相连all(v in G[u] for u, v in pairwise(nodes))。这一逻辑在 test_simple_paths.py 中有 13 个针对性用例覆盖包括空列表、平凡路径单节点、节点不在图中、重复节点、环路如[0, 1, 2, 0]、有向图方向、以及 MultiGraph / MultiDiGraph 中平行边场景[(0, 1), (0, 1)]依然构成[0, 1]的简单路径。典型使用示例 G nx.cycle_graph(4) nx.is_simple_path(G, [2, 3, 0]) True nx.is_simple_path(G, [0, 2]) False在有向图中方向敏感 G nx.DiGraph([(0, 1), (1, 2)]) nx.is_simple_path(G, [0, 1, 2]) # 沿边方向合法 True nx.is_simple_path(G, [2, 1, 0]) # 逆边方向不合法 Falseall_simple_paths枚举全部简单路径all_simple_paths(G, source, target, cutoffNone)生成图中从source到target的所有简单路径节点列表形式是模块中使用频率最高的函数。它返回的是一个生成器generator而不是一次性列表这一点对处理路径数量可能爆炸性增长的场景至关重要。参数说明参数类型说明GNetworkX graph任意图类型Graph、DiGraph、MultiGraph、MultiDiGraphsourcenode路径的起点若source不在图中抛出NodeNotFoundtargetnode 或 iterable of nodes单个节点或可迭代的多个终点节点若给定的不是图中节点且不可迭代抛出NodeNotFoundcutoffinteger, optional搜索深度上限只返回长度 ≤ cutoff的路径这里的路径长度按数学定义是len(path) - 1即边数。默认值为len(G) - 1从源码simple_paths.py可以看出all_simple_paths本身是all_simple_edge_paths的薄封装它先通过all_simple_edge_paths拿到边路径再把每条边路径转换为节点路径[source] [edge[1] for edge in edge_path]。完整示例在完全图上枚举从 0 到 3 的全部简单路径 G nx.complete_graph(4) for path in nx.all_simple_paths(G, source0, target3): ... print(path) [0, 1, 2, 3] [0, 1, 3] [0, 2, 1, 3] [0, 2, 3] [0, 3]用cutoff限制路径长度只返回长度 ≤ 2 的路径 paths nx.all_simple_paths(G, source0, target3, cutoff2) print(list(paths)) [[0, 1, 3], [0, 2, 3], [0, 3]]把每条路径转换成对应的边列表 paths nx.all_simple_paths(G, source0, target3) for path in map(nx.utils.pairwise, paths): ... print(list(path)) [(0, 1), (1, 2), (2, 3)] [(0, 1), (1, 3)] [(0, 2), (2, 1), (1, 3)] [(0, 2), (2, 3)] [(0, 3)]target支持多终点传可迭代对象一次遍历即可覆盖多个终点避免不必要的重复计算 G nx.complete_graph(4) for path in nx.all_simple_paths(G, source0, target[3, 2]): ... print(path) [0, 1, 2] [0, 1, 2, 3] [0, 1, 3] [0, 1, 3, 2] [0, 2] [0, 2, 1, 3] [0, 2, 3] [0, 3] [0, 3, 1, 2] [0, 3, 2]边界行为source 自身作为 targetsource到自身的单节点路径被认为是合法简单路径并被包含在结果中。all_simple_paths(G, source0, target0)返回[[0]]若target是一个同时包含source的集合如target{0, 1, 2}则会输出[[0], [0, 1], [0, 1, 2]]测试见 test_simple_paths.py。多图MultiGraph的平行边如果同一节点序列可以通过多条平行边到达则该节点序列会被返回多次每条平行边对应一次测试见 test_simple_paths.py G nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)]) list(nx.all_simple_paths(G, 0, 2)) [[0, 1, 2], [0, 1, 2]]cutoff 为 0 时除 source 恰好等于 target 外不会产生任何路径cutoff0且 source ≠ target 时结果为空见 test_simple_paths.py。DAG 根到叶的全路径枚举实战官方文档还演示了一个非常实用的组合用法用函数式编程风格一次性枚举有向无环图DAG中所有从根节点到叶节点的路径 from itertools import chain from itertools import product from itertools import starmap from functools import partial chaini chain.from_iterable G nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)]) roots (v for v, d in G.in_degree() if d 0) leaves (v for v, d in G.out_degree() if d 0) all_paths partial(nx.all_simple_paths, G) list(chaini(starmap(all_paths, product(roots, leaves)))) [[0, 1, 2], [0, 3, 2]]等价于循环写法且更高效将全部叶节点一次性作为target传入让搜索只跑一次 G nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)]) roots (v for v, d in G.in_degree() if d 0) leaves [v for v, d in G.out_degree() if d 0] all_paths [] for root in roots: ... paths nx.all_simple_paths(G, root, leaves) ... all_paths.extend(paths) all_paths [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]这类从根到叶枚举全部路径正是依赖关系分析、语法分析树遍历、状态机可达性检查等场景的常见需求。重要注意事项该函数不检查 source 与 target 之间是否存在路径。对于大图如果二者根本不可达搜索会遍历大量无谓的分支导致运行时间非常长。文档明确建议在大图上调用前先用has_path见 shortest_paths.rst 中的简化接口一节确认路径存在。时间复杂度单条路径可以在 $O(VE)$ 内找到但图中简单路径的总数可能极其庞大——例如 n 阶完全图中可达 $O(n!)$ 条。因此务必使用生成器按需消费而不是一次性list()全部物化。all_simple_edge_paths边视角的简单路径枚举all_simple_edge_paths(G, source, target, cutoffNone)与all_simple_paths功能等价但返回的是边列表而非节点列表。它是底层真正的实现all_simple_paths只是它的一层包装尤其适合需要同时获取路径上的边属性权重、颜色、容量等的场景多图场景下需要区分平行边边会带上 key的场景。参数与返回值参数说明G任意 NetworkX 图source/target同all_simple_paths单个节点或多个终点的可迭代对象节点缺失时抛NodeNotFoundcutoff深度上限这里边路径的长度就是边数。默认len(G) - 1返回值生成器产出边列表对多图边元素形式为(u, v, k)其中k是边 key示例普通图与多图 g nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)]) for path in sorted(nx.all_simple_edge_paths(g, 1, 4)): ... print(path) [(1, 2), (2, 4)] [(1, 3), (3, 4)]多图中返回的边带 key mg nx.MultiGraph() mg.add_edge(1, 2, keyk0) k0 mg.add_edge(1, 2, keyk1) k1 mg.add_edge(2, 3, keyk0) k0 for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)): ... print(path) [(1, 2, k0), (2, 3, k0)] [(1, 2, k1), (2, 3, k0)]cutoff效果示例 g nx.Graph([(1, 2), (2, 3), (3, 4), (4, 5), (1, 4), (1, 5)]) for path in sorted(nx.all_simple_edge_paths(g, 1, 5)): ... print(path) [(1, 2), (2, 3), (3, 4), (4, 5)] [(1, 4), (4, 5)] [(1, 5)] for path in sorted(nx.all_simple_edge_paths(g, 1, 5, cutoff1)): ... print(path) [(1, 5)]边界行为空路径当source本身是target之一时从source出发不经过任何边的空路径是合法的简单边路径会被输出即[]见 test_simple_paths.py G nx.Graph() G.add_node(0) paths list(nx.all_simple_edge_paths(G, 0, 0)) len(paths) 1自环忽略all_simple_edge_paths会忽略自环边test_simple_paths.py 中G nx.Graph([(0, 0), (0, 1), (1, 1), (1, 2)])从 0 到 2 只输出[(0, 1), (1, 2)]。源/目标缺失source不在图中或target既不是图中节点也不能作为可迭代对象解析时抛出nx.NodeNotFound。底层实现用显式栈模拟 DFS与直觉不同all_simple_edge_paths的递归式 DFS 在源码中被改造成了显式栈实现simple_paths.py这是为了避免 Python 深递归带来的调用栈溢出并让路径的枚举惰性化用current_path字典记录当前路径中每个节点是通过哪条边进入的既保证节点去重的快速查找O(1)成员判断又保留插入顺序栈中每个元素是当前路径最末端节点的出边迭代器每次循环取栈顶迭代器中的下一条未访问节点的边若到达targets则 yield 一条路径若len(current_path) - 1 cutoff且还有未覆盖的 target 可追求则把新节点压入current_path并推入新的边迭代器当栈顶迭代器耗尽时回溯stack.pop()current_path.popitem()。这种路径字典 出边迭代器栈的设计让多图平行边同一(u, v)有多条边天然地被分别枚举也正是节点路径会被重复输出的原因。shortest_simple_paths按长度从短到长输出简单路径shortest_simple_paths(G, source, target, weightNone)是模块中功能最强的函数它生成从source到target的全部简单路径且按路径长度或加权总代价从短到长排序非常适合前 K 条最短路径K Shortest Paths, KSP类问题。参数与约束参数类型说明GNetworkX graph仅限普通 Graph / DiGraph对 MultiGraph / MultiDiGraph 抛NetworkXNotImplemented由not_implemented_for(multigraph)装饰器保证见 simple_paths.pysource/targetnode单一节点不在图中抛NodeNotFoundweightstring 或 function可选边的权重来源默认None所有边权重视为 1weight参数的两种形式字符串边属性名。例如weightweight表示使用每条边的weight属性值。函数自定义权重函数必须接受恰好三个位置参数边的两个端点 u、v以及该边的属性字典返回一个数值或None。返回None表示隐藏该边——这是实现只走红色边的最短路径这类过滤需求的官方推荐手法weight lambda u, v, d: 1 if d[color] red else None这个用法在 test_simple_paths.py 中有对应测试权重函数对非相邻边返回None后shortest_simple_paths(G, 0, 2, weightcost)只会输出[[0, 1, 2], [0, 4, 3, 2]]。异常NetworkXNoPathsource 与 target 之间不存在任何路径test_simple_paths.py。NetworkXErrorsource 或 target 不在图中。NetworkXNotImplemented输入是 Multi[Di]Graph。示例环图上的按长度排序 G nx.cycle_graph(7) paths list(nx.shortest_simple_paths(G, 0, 3)) print(paths) [[0, 1, 2, 3], [0, 6, 5, 4, 3]]第一条是长度为 3 的短路径第二条是长度为 4 的绕行路径严格按长度递增输出。实战实现 K 条最短路径官方文档给出了用itertools.islice包装成 K 最短路径工具的标准写法 from itertools import islice def k_shortest_paths(G, source, target, k, weightNone): ... return list( ... islice(nx.shortest_simple_paths(G, source, target, weightweight), k) ... ) for path in k_shortest_paths(G, 0, 3, 2): ... print(path) [0, 1, 2, 3] [0, 6, 5, 4, 3]加权场景与测试验证带权重的正确性在测试中有严格验证test_weighted_shortest_simple_path会为完全图的每条边随机赋 1~100 的权重然后断言输出路径的累计代价单调不减test_simple_paths.py。test_Greg_Bernstein则验证了一个带weight、capacity、name等多属性的真实小网络输出必须严格等于[[N1, N0, N3], [N1, N2, N3], [N1, N4, N0, N3]]test_simple_paths.py。注意不允许负权重。文档明确指出如果使用加权最短路径搜索不允许负权重simple_paths.py底层_bidirectional_dijkstra在遇到负权导致矛盾路径时甚至会抛出ValueError(Contradictory paths found: negative weights?)。底层原理Yen 算法 双向搜索shortest_simple_paths的实现基于 Jin Y. Yen 于 1971 年提出的 K 最短无环路径算法simple_paths.py找到前 K 条路径需要 $O(KN^3)$ 次操作。核心流程simple_paths.py用最短路径算法求第一条路径压入候选缓冲listBPathBuffer见 simple_paths.py内部用堆保证按代价弹出、用 set 去重对当前最短路径的每个前缀作为根路径root把根路径上的节点加入ignore_nodes、把已出现过的同前缀路径的下一跳边加入ignore_edges然后求偏离路径spur path——即从根路径末端出发、绕开已用节点和边的修正最短路径拼成完整候选所有候选压入listB弹出代价最小的那条作为下一条结果如此循环直至候选为空。其中求偏离路径时无权重情况下使用自定义的双向 BFS_bidirectional_shortest_path有权重情况下使用双向 Dijkstra_bidirectional_dijkstrasimple_paths.py。这两个函数都支持ignore_nodes/ignore_edges参数用于在 Yen 算法的迭代中屏蔽已探索过的节点与边它们本质上是对 unweighted 与 weighted 模块中双向最短路径实现的定制修改版。双向搜索的意义在于普通 Dijkstra 从 source 向外球面式扩展而双向版本同时从 source 和 target 两个方向扩展两个半径减半的球面总体积约为单向前的一半因此实践中双向 Dijkstra 比普通 Dijkstra 快不止两倍源码注释中给出了这个几何直观解释见 simple_paths.py。四个 API 的选型对比与适用场景需求推荐函数输出形式支持多图支持多终点有序性判断一个节点序列是否合法is_simple_path布尔值是——枚举全部简单路径all_simple_paths节点列表生成器是平行边分别计数是iterable target无保证枚举全部简单路径边视角all_simple_edge_paths边列表生成器是边带 key是iterable target无保证按长度/代价从短到长输出shortest_simple_paths节点列表生成器否抛异常否单 target严格递增选型要点只需要任意一条最短路径时应使用 shortest_path见 shortest_paths.rst 的简化接口它的开销远低于枚举式函数需要全部最短路径同长度时用all_shortest_paths需要前 K 条最短路径按长度递增时用shortest_simple_pathsislice需要全部简单路径不限长度时用all_simple_paths/all_simple_edge_paths并配合cutoff控制爆炸式的路径数量大图调用枚举函数前先用has_path确认可达性避免无谓的长时间搜索。快速上手指引所有四个函数都通过networkx.algorithms包直接导出见 algorithms/init.py 中的from networkx.algorithms.simple_paths import *因此可以直接以nx.xxx形式调用无需额外导入子模块。安装 NetworkX 后参考 INSTALL.rst 与 pyproject.toml即可按本文示例运行。综合示例一个同时覆盖四种能力的完整片段。import networkx as nx from itertools import islice # 构造一个带权重的有向图 G nx.DiGraph() G.add_weighted_edges_from([ (A, B, 4), (A, C, 2), (B, C, 5), (B, D, 10), (C, E, 3), (E, D, 4), (D, F, 11), ]) # 1) 校验路径 nx.is_simple_path(G, [A, B, D, F]) # True # 2) 枚举全部简单路径限制长度 3 list(nx.all_simple_paths(G, A, F, cutoff3)) # 3) 边视角枚举 list(nx.all_simple_edge_paths(G, A, F)) # 4) 前 3 条按权重最短的简单路径 list(islice(nx.shortest_simple_paths(G, A, F, weightweight), 3))延伸阅读本文涉及的四个函数定义与完整 docstring 见 networkx/algorithms/simple_paths.py边界行为均有测试用例佐证见 networkx/algorithms/tests/test_simple_paths.py与简单路径密切相关的单条最短路径、全部等长最短路径、可达性判断等 API 见 最短路径文档节点路径与边路径的互转工具pairwise见 networkx/utils/misc.py模块的 autodoc 参考页本文的源头文档见 doc/reference/algorithms/simple_paths.rst。【免费下载链接】networkxNetwork Analysis in Python项目地址: https://gitcode.com/gh_mirrors/ne/networkx创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考