| sidebar_position | 2 |
|---|
算子类别：Path（路径、可达性、巡回与关键路径）
算法数量：19 个
适用阶段：路线规划、依赖链分析、可达性判定、全局距离评估、巡回/遍历设计、路径枚举、启发式寻路、环路检测
产品定位：为“怎么走最短/最省”、“有没有路可达”、“有哪些可行路径”、“如何遍历所有边”、“是否存在环路”、“DAG 中最长依赖链/关键路径是什么”、“是否存在哈密顿路径”提供统一的路径能力底座。
Path 算子集面向各类图结构，包括交通路网、通信拓扑、调用依赖、交易链路、知识引用网、任务流程图、巡检网络等，覆盖以下核心问题：
-
最短路径计算
- 两点之间最短路径是什么？
- 最短距离/成本是多少？
- 是否需要支持非负权、负权或启发式搜索？
-
全局距离评估
- 任意两点之间的最短距离是多少？
- 网络整体平均路径长度是多少？
- 稠密图和稀疏图应选择哪类全对最短路算法？
-
可达性与路径枚举
- A 是否可以到达 B？
- A 到 B 有哪些简单路径？
- 多条备选最短简单路径是什么？
-
DAG 关键路径分析
- DAG 中最长依赖链是什么？
- 关键路径总长度是多少？
-
欧拉路径与巡回
- 是否可以遍历每条边恰好一次？
- 是否存在欧拉路径或欧拉回路？
- 如何生成对应的边遍历顺序？
-
环路与特殊路径
- 图中是否存在环？
- 是否存在哈密顿路径？
- 如何寻找或验证复杂路径结构？
| 目标 | 推荐算子 | 什么时候用 |
|---|---|---|
| 判断图中是否存在环 | find_cycle |
依赖图、调用图、流程图中需要快速发现环路风险 |
| A→B 最短“路径序列” | shortest_path / dijkstra_path / bellman_ford_path / astar_path |
需要输出具体经过哪些节点 |
| A→B 最短“距离值” | dijkstra_path_length |
只关心最短距离、最低成本、最短耗时 |
| 非负权图最短路径 | dijkstra_path, dijkstra_path_length |
边权均为非负，例如距离、时间、成本 |
| 启发式最短路径搜索 | astar_path |
路网、地图、空间搜索中有启发函数可用 |
| 可能存在负权边 | bellman_ford_path / goldberg_radzik |
成本模型中存在补贴、返利、负收益等；不能有负环 |
| 任意两点最短路距离，稠密图 | floyd_warshall |
节点规模中等、边较多，需要完整距离矩阵 |
| 任意两点最短路路径，稀疏图 | johnson |
大规模稀疏图，可含负权边但不能有负环 |
| 图的平均最短路径长度 | average_shortest_path_length |
衡量网络效率、平均跳数、小世界特征 |
| 判断 A 是否可达 B | has_path |
只需要 Yes/No，不需要具体路径 |
| 枚举所有简单路径 | all_simple_paths |
需要分析所有不重复节点的可行路径 |
| 输出多条最短简单路径 | shortest_simple_paths |
需要备选路线、候选链路、Top-K 路径方案 |
| DAG 的关键路径 | dag_longest_path, dag_longest_path_length |
项目排期、依赖链、流程耗时分析 |
| 判断是否存在欧拉回路 | is_eulerian |
巡检、道路覆盖、链路逐边遍历前置判断 |
| 生成欧拉路径 | eulerian_path |
每条边恰好经过一次，不要求回到起点 |
| 生成欧拉回路 | eulerian_circuit |
每条边恰好经过一次，并回到起点 |
| 寻找哈密顿路径 | hamiltonian_path |
需要访问每个节点恰好一次的路径结构 |
-
输入
G：NetworkX 图对象- 可为无向图
Graph - 可为有向图
DiGraph - 部分算法支持
MultiGraph/MultiDiGraph
- 可为无向图
-
常见参数
source：起点节点target：终点节点weight：边权字段名或权重函数cutoff：路径搜索最大深度或最大路径长度heuristic：A* 算法中的启发函数keys：多重图中是否返回边 key
-
权重语义
- 最短路类：
weight通常表示距离、成本、时间，数值越小越优 - DAG 最长路类：
weight通常表示时长、收益、累计成本，数值越大越“长”
- 最短路类：
-
常见输出
- 路径：节点序列
list[node] - 距离：数值型距离 / 成本
- 全对最短路：
dict[source][target] -> dist/path - 欧拉路径 / 回路：边序列迭代器
- 可达性 / 判定类：
bool - 路径枚举类：路径迭代器
- 路径：节点序列
注意：在多重图中，平行边可能代表不同道路、不同链路或不同交易关系。若需要区分具体边，应结合边 key 或边属性进行处理。
功能说明
在图中寻找一个环。如果图中存在环，则返回构成该环的边序列；如果不存在环，通常会抛出无环异常或返回空结果，具体取决于封装方式。
产品价值
- 快速发现依赖环、调用环、流程闭环
- 是 DAG 校验、拓扑排序前的重要诊断能力
- 可帮助定位导致流程无法线性执行的关键关系
典型场景
- 项目任务循环依赖检测
- 数据血缘闭环检测
- 服务调用环检测
- 审批流程回路排查
- 知识引用环路分析
适用与特性
- 图类型：有向图 / 无向图
- 输出：边序列
- 复杂度：通常
O(V + E)
功能说明
计算图中两点间、单源到多点或全源之间的最短路径。无权图中按边数计算，有权图中按指定 weight 字段或函数计算。
产品价值
- 提供统一的最短路径入口
- 可根据是否指定
source、target灵活返回单对、单源或全源结果 - 适合产品中作为默认路径查询能力
典型场景
- 从 A 到 B 的最短路线
- 依赖链最短解释路径
- 网络路由最小跳数路径
- 知识图谱实体间最短关联链路
关键参数
source：起点，可选target：终点，可选weight：边权字段或函数method：有权场景下可选择dijkstra或bellman-ford
适用与特性
- 图类型：有向图 / 无向图
- 输出：节点路径或路径字典
- 复杂度：取决于是否有权以及查询范围
功能说明
在边权非负的图中，计算从 source 到 target 的最短路径，并返回节点序列。
产品价值
- 工程上最常用的加权最短路径算法之一
- 对非负权重场景性能稳定
- 路径结果直观，便于展示和解释
典型场景
- 物流路径规划
- 通信网络最小时延路由
- 交通路网最短时间路径
- 成本最小的服务调用路径
关键参数
source：起点target：终点weight：距离、时间、成本等边权字段
适用与特性
- 图类型：有向图 / 无向图
- 要求：边权非负
- 输出：节点序列
- 复杂度：常见为
O(E + V log V)
功能说明
计算从 source 到 target 的最短路径长度，只返回距离或成本值，不返回具体路径。
产品价值
- 适合只需要指标值、不需要路线细节的场景
- 相比返回完整路径，结果更轻量
- 可用于批量距离评估或阈值判断
典型场景
- 两点间最短距离查询
- 最低物流成本估算
- 最小时延评估
- 风险传播最短跳数评估
关键参数
source：起点target：终点weight：边权字段或函数
适用与特性
- 图类型：有向图 / 无向图
- 要求：边权非负
- 输出：数值型距离
- 复杂度：常见为
O(E + V log V)
功能说明
计算从 source 到 target 的最短路径，支持负权边，但不能存在从起点可达的负权环。
产品价值
- 适用于权重中存在补贴、返利、负成本的场景
- 可作为 Dijkstra 不适用时的替代方案
- 能处理更复杂的成本建模
典型场景
- 费用模型含返利或补贴
- 金融交易净成本路径
- 风控链路中的负收益建模
- 带惩罚和奖励的路径计算
关键参数
source：起点target：终点weight：边权字段，默认通常为"weight"
适用与特性
- 图类型：有向图 / 无向图
- 支持：负权边
- 不支持：负权环
- 输出：节点序列
- 复杂度：约
O(VE)
功能说明
Goldberg-Radzik 是一种用于单源最短路径问题的算法，可处理负权边，并检测负权环。
产品价值
- 适合存在负权边的单源最短路场景
- 在部分图结构上相比传统 Bellman-Ford 具有更好的实际性能
- 适合复杂成本网络中的路径计算和异常检测
典型场景
- 含负成本的交易网络
- 带补贴的路线成本分析
- 奖惩混合的路径优化
- 负权环风险检测
关键参数
source：起点weight：边权字段或函数
适用与特性
- 图类型：有向图 / 无向图
- 支持：负权边
- 可检测：负权环
- 输出：距离与前驱信息
- 复杂度：最坏情况下仍可能较高，适合中等规模负权图分析
功能说明
基于动态规划一次性计算图中任意两点之间的最短路径距离，返回完整距离结构。
产品价值
- 适合需要完整距离矩阵的场景
- 对稠密图较直观稳定
- 可作为网络全局距离分析的基础能力
典型场景
- 城市之间全局最短距离矩阵
- 小规模网络全对距离分析
- 路网整体可达成本评估
- 图布局或相似度计算前置处理
关键参数
weight：边权字段名，默认通常为"weight"
适用与特性
- 图类型：有向图 / 无向图
- 输出：
dict[source][target] -> distance - 复杂度：
O(V^3) - 适合：节点规模中等、边较密的图
功能说明
Johnson 算法用于计算稀疏图中的全对最短路径，可处理负权边，但不能存在负权环。
产品价值
- 适合大规模稀疏图的任意两点路径计算
- 相比 Floyd-Warshall，在稀疏图中通常更高效
- 可用于带负权边的全局路径分析
典型场景
- 大规模交通网络
- 通信网络全对路由分析
- 知识图谱实体全局路径分析
- 含负权的稀疏交易网络
关键参数
weight：边权字段名或函数
适用与特性
- 图类型：有向图 / 无向图
- 支持：负权边
- 不支持：负权环
- 输出：全对最短路径字典
- 复杂度：约
O(VE + V^2 log V)
功能说明
计算图中所有节点对之间最短路径长度的平均值，用于衡量网络整体连通效率或平均跳数。
产品价值
- 反映网络整体可达效率
- 可用于判断网络是否具有“小世界”特征
- 是复杂网络分析中的常用全局指标
典型场景
- 社交网络平均人际距离
- 通信网络平均传输跳数
- 交通网络平均出行成本
- 知识网络平均关联距离
- 组织协作网络效率评估
关键参数
weight：是否使用边权method：可选择无权、多次 Dijkstra、Bellman-Ford、Floyd-Warshall 等方法
适用与特性
- 图类型：通常要求连通图；有向图通常要求强连通
- 输出：数值型平均距离
- 复杂度：取决于底层最短路方法
功能说明
判断图中是否存在从 source 到 target 的路径。
产品价值
- 快速回答“能不能到”
- 不需要计算完整路径，适合高频查询
- 可作为路径计算前置过滤
典型场景
- A 服务是否能调用到 B 服务
- 某资金账户是否能流向目标账户
- 某任务是否会影响另一个任务
- 某知识点是否可推导到另一个知识点
关键参数
source：起点target：终点
适用与特性
- 图类型：有向图 / 无向图
- 输出：
bool - 复杂度：最坏
O(V + E)
功能说明
在有向无环图（DAG）中计算最长路径，并返回对应的节点序列。
产品价值
- 识别最长依赖链
- 支持关键路径分析
- 可用于项目排期、流程耗时和任务依赖优化
典型场景
- 项目管理关键路径
- 工作流最长耗时链
- 数据处理流水线瓶颈链路
- 课程先修依赖最长学习路径
- 调用链最大累计耗时分析
关键参数
weight：边权字段，表示时长、成本或收益default_weight：无权边默认权重topo_order：可传入已有拓扑序以复用计算结果
适用与特性
- 图类型：DAG
- 输出：节点序列
- 复杂度：
O(V + E)
功能说明
计算 DAG 中最长路径的累计长度或权重，只返回长度值，不返回具体路径。
产品价值
- 快速获得关键路径总耗时或总成本
- 适合指标看板、风险评估、排期估算
- 可与
dag_longest_path搭配使用
典型场景
- 项目最短完工时间估算
- 流程最大耗时评估
- 依赖链最大累计风险
- DAG 网络中最长传播距离
关键参数
weight：边权字段default_weight：默认边权
适用与特性
- 图类型：DAG
- 输出：数值型长度
- 复杂度：
O(V + E)
功能说明
判断图是否存在欧拉回路，即是否可以从某个节点出发，遍历每条边恰好一次后回到起点。
产品价值
- 是欧拉回路生成前的前置校验
- 可判断巡检网络是否支持闭环一次性覆盖
- 支持道路、线路、管网、链路覆盖分析
典型场景
- 道路巡检闭环规划
- 管线巡检路径设计
- 邮递员问题前置判定
- 网络链路全覆盖遍历
- 电路连线检查
判定直观理解
- 无向图：所有相关节点度数为偶数，且连通
- 有向图：每个节点入度等于出度，并满足连通性条件
适用与特性
- 图类型：有向图 / 无向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
在满足条件时，生成一条遍历每条边恰好一次的路径，不要求起点和终点相同。
产品价值
- 适合需要覆盖所有边、但不强制回到起点的场景
- 可用于巡检、清扫、链路追踪等任务
- 直接输出可执行的边遍历顺序
典型场景
- 道路清扫路径
- 管网逐段巡检
- 交易链路逐边排查
- 网络链路覆盖测试
- 一笔画路径生成
关键参数
source：可选起点keys：多重图中是否返回边 key
适用与特性
- 图类型：有向图 / 无向图 / 部分多重图
- 输出：边序列迭代器
- 复杂度：通常
O(E)
功能说明
生成一条欧拉回路：从指定或任意起点出发，遍历每条边恰好一次，并最终回到起点。
产品价值
- 适合闭环巡检和闭环覆盖任务
- 能输出完整的边访问顺序
- 常用于路径规划、线路巡检和拓扑覆盖
典型场景
- 闭环道路巡检
- 电力线路全覆盖巡查
- 通信链路测试
- 物流车辆回仓路线
- 图结构一笔画闭环分析
关键参数
source：指定起点keys：多重图中是否输出边 key
适用与特性
- 图类型：有向图 / 无向图 / 多重图
- 输出：边序列迭代器
- 复杂度：通常
O(E)
功能说明
使用 A* 算法计算从 source 到 target 的最短路径。A* 在 Dijkstra 的基础上引入启发函数，用于优先搜索更可能接近目标的方向。
产品价值
- 在空间路网或地图搜索中通常比普通 Dijkstra 更高效
- 支持结合业务启发信息进行路径搜索
- 适合目标明确、存在合理距离估计函数的场景
典型场景
- 地图导航
- 游戏寻路
- 机器人路径规划
- 城市路网搜索
- 空间知识图谱路径搜索
关键参数
source：起点target：终点heuristic：启发函数，估计当前节点到目标节点的剩余成本weight：边权字段或函数
适用与特性
- 图类型：有向图 / 无向图
- 要求：启发函数应尽量不高估真实距离，以保证最优性
- 输出：节点序列
- 复杂度：取决于启发函数质量；最坏情况下可退化为 Dijkstra 类搜索
功能说明
枚举从 source 到 target 的所有简单路径。简单路径指路径中不重复经过同一个节点。
产品价值
- 用于完整分析两点之间所有可行关系链
- 支持风险传播路径、资金路径、依赖路径的全量枚举
- 适合小中规模图或设置深度限制后的路径探索
典型场景
- 两个账户之间所有资金链路
- 两个服务之间所有调用链
- 两个实体之间所有知识关联路径
- 供应链替代路径分析
- 风险传导路径枚举
关键参数
source：起点target：终点cutoff：最大路径长度，建议工程中设置
适用与特性
- 图类型：有向图 / 无向图
- 输出：路径迭代器
- 注意：路径数量可能指数级增长
- 适合：小图或有限深度路径分析
功能说明
按照路径长度或权重从短到长，生成从 source 到 target 的简单路径序列。常用于获取 Top-K 条备选路径。
产品价值
- 不只给出一条最短路径，而是按优先级生成多条候选路径
- 适合路线备选、链路容灾和方案比较
- 相比全量枚举，更适合按需取前 K 条结果
典型场景
- 导航中的多条备选路线
- 网络路由备份路径
- 供应链替代方案
- 风控调查中的最短可疑链路候选
- 服务调用链容灾路径分析
关键参数
source：起点target：终点weight：边权字段或函数
适用与特性
- 图类型：通常用于简单图
- 输出：路径生成器
- 使用建议：结合
itertools.islice或产品参数限制 Top-K 数量
功能说明
寻找一条经过图中每个节点恰好一次的路径。与欧拉路径关注“每条边一次”不同，哈密顿路径关注“每个节点一次”。
产品价值
- 用于访问所有节点且不重复访问的路径规划
- 可表达任务、站点、实体的一次性覆盖顺序
- 适合特殊结构图或中小规模图的组合路径分析
典型场景
- 站点一次性访问路径
- 任务节点覆盖顺序
- 旅游路线规划
- 图结构可遍历性分析
- 竞赛/排列类路径问题
适用与特性
- 图类型：有向图 / 无向图，具体支持取决于实现
- 输出：节点序列
- 注意：哈密顿路径问题通常计算复杂度较高，大规模图需谨慎使用
- 默认通用查询：
shortest_path - 非负权最短路径：
dijkstra_path - 只需要距离值：
dijkstra_path_length - 存在负权边：
bellman_ford_path/goldberg_radzik - 有空间启发函数：
astar_path
- 稠密图全对距离：
floyd_warshall - 稀疏图全对路径：
johnson - 网络平均距离：
average_shortest_path_length
- 只判断是否可达：
has_path - 枚举所有简单路径：
all_simple_paths - 获取多条候选短路径：
shortest_simple_paths
- 输出最长路径节点序列：
dag_longest_path - 只输出最长路径长度：
dag_longest_path_length - 使用前建议先确认图为 DAG：
is_directed_acyclic_graph
- 判断是否存在欧拉回路：
is_eulerian - 生成欧拉路径：
eulerian_path - 生成欧拉回路：
eulerian_circuit
- 查找图中的环：
find_cycle - 查找哈密顿路径：
hamiltonian_path
- “A 到 B 的最短路径是什么？请输出节点序列。”
- “A 到 B 的最短路长度是多少？”
- “该图中是否存在环？如果有，请返回一个环。”
- “该图是否存在从 A 到 B 的路径？”
- “请列出 A 到 B 的所有简单路径。”
- “请给出 A 到 B 的前 5 条最短备选路径。”
- “该网络的平均最短路径长度是多少？”
- “请计算任意两点之间的最短路径。”
- “在 DAG 中，最长依赖链包含哪些节点？”
- “关键路径总时长是多少？”
- “这个图是否存在欧拉回路？”
- “如果存在欧拉路径，请输出每条边的遍历顺序。”
- “是否存在一条经过所有节点且不重复的哈密顿路径？”
- “这个路网能否设计成一次性覆盖所有边的巡检路线？”
-
权重语义必须统一
- 最短路中，权重通常表示距离、时间、成本，越小越优。
- DAG 最长路中，权重通常表示时长、收益、累计成本，越大越长。
- 同一张图中混用多个权重字段时，需要明确字段含义。
-
负权边要谨慎选择算法
- 非负权：优先使用
dijkstra_path/dijkstra_path_length - 存在负权边：使用
bellman_ford_path/goldberg_radzik - 全对负权边场景：使用
johnson - 存在负权环时，最短路径可能没有定义。
- 非负权：优先使用
-
按图规模选择全对算法
- 稠密图、节点数中等：
floyd_warshall - 稀疏图、节点数较大：
johnson
- 稠密图、节点数中等：
-
路径枚举要控制规模
all_simple_paths可能产生指数级结果。- 工程中建议设置
cutoff或限制返回条数。 - 多候选路径优先使用
shortest_simple_paths按需取 Top-K。
-
欧拉类算法建议先判定
- 先使用
is_eulerian或检查度数条件。 - 再调用
eulerian_circuit或eulerian_path。 - 多重图中注意是否需要返回 edge key。
- 先使用
-
DAG 最长路径必须保证无环
dag_longest_path和dag_longest_path_length只适用于 DAG。- 使用前建议先通过 DAG 判定能力进行校验。
-
A 算法依赖启发函数质量*
- 启发函数越接近真实剩余距离，搜索效率越高。
- 若启发函数高估真实距离，可能影响最优性。
- 无有效启发函数时，可退回 Dijkstra。
-
哈密顿路径计算成本高
- 哈密顿路径问题通常难度较高。
- 更适合中小规模图、特殊结构图或启发式分析。
- 大图场景应谨慎使用，必要时结合剪枝或近似方法。
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | find_cycle |
查找图中的环 |
| 2 | shortest_path |
通用最短路径 |
| 3 | dijkstra_path |
Dijkstra 最短路径 |
| 4 | dijkstra_path_length |
Dijkstra 最短路径长度 |
| 5 | bellman_ford_path |
Bellman-Ford 最短路径 |
| 6 | goldberg_radzik |
Goldberg-Radzik 单源最短路径 |
| 7 | floyd_warshall |
Floyd-Warshall 全对最短路 |
| 8 | johnson |
Johnson 全对最短路 |
| 9 | average_shortest_path_length |
平均最短路径长度 |
| 10 | has_path |
可达性判定 |
| 11 | dag_longest_path |
DAG 最长路径 |
| 12 | dag_longest_path_length |
DAG 最长路径长度 |
| 13 | is_eulerian |
欧拉图判定 |
| 14 | eulerian_path |
欧拉路径 |
| 15 | eulerian_circuit |
欧拉回路 |
| 16 | astar_path |
A* 启发式最短路径 |
| 17 | all_simple_paths |
所有简单路径枚举 |
| 18 | shortest_simple_paths |
最短简单路径枚举 |
| 19 | hamiltonian_path |
哈密顿路径 |