跳到主要内容

Path 路径算子集

算子类别：Path（路径与可达性）

适用阶段：路线规划、依赖链分析、可达性判定、全局距离评估、巡回/遍历设计

产品定位：为“怎么走最短/最省”、“有没有路可达”、“如何遍历所有边”、“在 DAG 中最长依赖链/关键路径是什么”提供统一的路径能力底座。

一、算子集概述​

Path 算子集面向各类图结构（交通路网、通信拓扑、调用依赖、交易链路、知识引用网等），覆盖三大类核心问题：

  1. 单源/单对最短路：从 A 到 B 的最短路径/最短距离（shortest_path, dijkstra_path, dijkstra_path_length, bellman_ford_path）
  2. 全源最短路/平均距离：任意两点最短路距离矩阵、网络“平均跳数/平均距离”（floyd_warshall, johnson, average_shortest_path_length）
  3. 可达性与结构性路径：是否存在路径、DAG 最长路径（关键路径）、欧拉路径/回路（遍历每条边一次）（has_path, dag_longest_path, dag_longest_path_length, is_eulerian, eulerian_path, eulerian_circuit）

二、能力分类与选型建议​

目标推荐算子什么时候用
A→B 最短“路径序列”shortest_path / dijkstra_path / bellman_ford_path需要具体走法（节点序列）
A→B 最短“距离值”dijkstra_path_length只要最短距离/成本
可能存在负权边bellman_ford_path（单对/单源）或 johnson（全对）例如补贴、返利、负收益等；但不能有负环
任意两点最短路距离（稠密图）floyd_warshall节点不太多（V 中等），但边较多
任意两点最短路距离（稀疏图）johnsonV 大、E 相对稀疏；可含负权（无负环）
图的“平均最短距离/平均跳数”average_shortest_path_length衡量网络效率、小世界程度等
只判定“能不能到”has_path需要 Yes/No 可达性
DAG 的关键路径/最长依赖链dag_longest_path / dag_longest_path_length调度、项目管理、依赖编排
遍历每条边恰好一次（开/闭）eulerian_path / eulerian_circuit（+ 先用 is_eulerian 判断）巡检、道路覆盖、链路逐边追踪

三、通用输入输出约定​

  • 输入 G：NetworkX 图对象（有向/无向；部分算法支持 multigraph；部分支持权重）
  • 权重解释：
    • 最短路类：weight 通常被解释为 距离/成本/时间（越小越优）
    • DAG 最长路类：weight 被解释为 时长/收益/累积成本（越大越“长”）
  • 输出：
    • 路径：节点序列 list[node]
    • 距离矩阵/全对最短路：dict[source][target] -> dist 或 dict[(source,target)] -> dist
    • 欧拉路径/回路：边序列迭代器（或可转节点序列）

注意：不少最短路函数在 multigraph 上会将平行边视作多条候选边；如果需要区分边 key，请使用 keys=True 或读取边属性时显式处理。

四、算子详细说明​

1) shortest_path —— 通用最短路径（单对 / 单源 / 全源）​

功能说明
计算图中两点间或多点间的最短路径（返回节点序列）。当 weight=None 时视为无权图（每条边长度为 1），否则按 weight 作为边权。

典型场景

  • GPS/物流：从 A 到 B 的最短距离/最短耗时路线
  • 引用/依赖链：从基础节点到目标节点的最短链路（最少中间节点）
  • 网络路由：最小延迟/最小成本传输路径

关键参数（调优）

  • source / target：指定后可显著减少计算量与输出规模
  • weight：None（无权）/ 字段名 / 函数
  • method：dijkstra 或 bellman-ford（有权时）

复杂度

  • 无权：通常 O(V+E)（BFS）
  • 加权（Dijkstra）：常见 O(E + V log V)（堆优化）
  • 加权（Bellman-Ford）：约 O(VE)

可直接回答的问题（示例）

  • “请找 A 到 B 的最短路径，并输出节点序列。”
  • “从起点 S 到所有可达节点的最短路径分别是什么？”

2) dijkstra_path —— Dijkstra 最短路径（返回路径序列）​

功能说明
在边权非负的图中，计算从 source 到 target 的最短路径（节点序列）。

产品价值

  • 工程上最常用的最短路算法之一，性能好、解释清晰
  • 支持权重字段名或自定义权重函数（可隐藏边：返回 None）

关键参数（调优）

  • weight：字段名或函数（常用：distance/time/cost）

复杂度
O(E + V log V)（典型实现）

3) dijkstra_path_length —— Dijkstra 最短路径长度（只返回距离）​

功能说明
同 Dijkstra，但只输出最短距离/成本值（不返回具体节点序列）。

典型场景

  • 只关心“最低费用/最低时延/最短公里数”而不需要路线细节

复杂度
O(E + V log V)

4) bellman_ford_path —— Bellman-Ford 最短路径（支持负权）​

功能说明
计算从 source 到 target 的最短路径（节点序列），可处理负权边（但不能存在负权环）。

典型场景

  • 费用模型含补贴/返利导致某些边为负
  • 风控/收益：边权可表示“净成本/净收益（取相反数）”的传导

关键参数（调优）

  • weight：字段名或函数（默认 "weight"）
  • source / target：指定单对路径

复杂度
O(VE)

5) floyd_warshall —— Floyd-Warshall 全对最短路（距离字典）​

功能说明
基于动态规划一次性计算任意两点的最短路径距离，返回 dist[u][v]。

适用特点

  • 更适合 稠密图 或需要一次性得到完整距离矩阵的任务
  • 节点数较大时开销很高（立方复杂度）

关键参数（调优）

  • weight：边权字段名（默认 "weight"）

复杂度
O(V^3)

6) johnson —— Johnson 全对最短路（稀疏图友好，可含负权）​

功能说明
为稀疏图计算任意两点最短路。可处理负权边（无负环），通常比 Floyd-Warshall 更适合大规模稀疏网络。

关键参数（调优）

  • weight：字段名或自定义函数（可实现动态权重/规则）

复杂度
约 O(VE + V^2 log V)（工程实现常见）

7) average_shortest_path_length —— 平均最短路径长度（网络效率）​

功能说明
计算图中所有可达节点对的最短路径长度的平均值，用于衡量网络整体“连通效率/平均跳数”。

典型场景

  • 社交网络：平均需要经过多少个中间人
  • 通信/交通网络：平均时延/平均换乘次数
  • 复杂网络分析：小世界性质、整体可达性

关键参数（调优）

  • weight：None/字段名/函数（决定用无权还是加权距离）
  • method：unweighted / dijkstra / bellman-ford / floyd-warshall 等

复杂度（取决于 method 与图结构）

  • 常见为 O(V*(V+E))（无权 BFS 多次）或 O(V*(E + V log V))（多次 Dijkstra）

8) has_path —— 可达性判定（Yes/No）​

功能说明
判断图中两点之间是否存在路径（可达性）。常用 DFS/BFS。

典型场景

  • “A 能否到达 B？”的快速校验
  • 连通性约束检查（依赖链是否可达、路网是否断裂）

复杂度
O(V+E)（最坏）

9) dag_longest_path —— DAG 最长路径（返回节点序列）​

功能说明
在**有向无环图（DAG）**中计算最长路径（按边权累积，支持缺省权重）。可提供拓扑序以加速或复用。

典型场景

  • 项目管理/调度：关键路径（Critical Path）
  • 工作流优化：最长依赖链、最大累计耗时链
  • 引用链：从基础论文到前沿综述的最长“顺序阅读链”

关键参数（调优）

  • weight：边权字段名（默认 "weight"）
  • default_weight：无权边的默认权重（默认 1）
  • topo_order：外部提供拓扑序（None 时算法内部计算）

复杂度
O(V+E)（线性，适合大 DAG）

10) dag_longest_path_length —— DAG 最长路径长度（返回长度值）​

功能说明
与 dag_longest_path 类似，但只返回最长路径的累计权重/长度。

关键参数（调优）

  • weight、default_weight

复杂度
O(V+E)

11) is_eulerian —— 是否存在欧拉回路（Eulerian Circuit）​

功能说明
判断图是否为欧拉图，即是否存在一条从同一节点出发并回到该节点、且每条边恰好经过一次的回路。

判定要点（直观理解）

  • 无向图：所有节点度为偶数（且相关部分连通）
  • 有向图：入度=出度（且相关部分强连通/连通满足条件）

复杂度
O(V+E)

12) eulerian_path —— 欧拉路径（Eulerian Trail，开路）​

功能说明
在满足条件时，返回一条遍历每条边恰好一次的路径（不要求首尾相同）。
常见存在条件：无向图恰有 0 或 2 个奇度节点；有向图满足入出度差约束等。

典型场景

  • 垃圾清运/巡检：希望“每条路走一次”，不强制回到起点
  • 电路/布线：一次性覆盖所有连线而不重复

复杂度
O(E)（构造型算法，常见近线性）

13) eulerian_circuit —— 欧拉回路（闭路，返回边序列迭代器）​

功能说明
返回一条欧拉回路：从 source 出发，遍历每条边恰好一次并回到 source。支持有向/无向、支持 multigraph；可选择是否输出 edge key。

关键参数（调优）

  • source：指定起点；不指定则任选一个
  • keys：multigraph 下是否输出 (u,v,k) 以区分平行边

复杂度
O(E)

五、可直接回答的典型问题（汇总示例）​

  • “A 到 B 最短路径是什么？请输出节点序列。”
  • “A 到 B 的最短路长度是多少（按 cost 权重）？”
  • “该图是否存在欧拉回路？若存在请给出一条回路的遍历顺序。”
  • “在 DAG 中，最长依赖链（关键路径）包含哪些节点？总时长是多少？”
  • “请输出该网络的平均最短路径长度，用于评估整体连通效率。”
  • “请计算任意两点间最短路距离矩阵（全对最短路）。”

六、工程落地注意事项​

  1. 权重语义要统一：最短路中权重越小越优；最长路（DAG）中权重越大越“长”。同一张图混用时要明确字段/正负号。
  2. 负权边选择：只要存在负权边，Dijkstra 不适用；选 Bellman-Ford（单源/单对）或 Johnson（全对）。
  3. 规模选择算法：
    • 稠密、V 中等：floyd_warshall
    • 稀疏、V 大：johnson
    • 单对：dijkstra_path / bellman_ford_path
  4. 欧拉类先判定：实际工程建议先 is_eulerian 或检查度条件，再求 eulerian_path/circuit，避免异常与无解情况。