本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为给定顶点的有向路径的多种方法，涵盖内置算法适配技巧与自定义动态规划实现，重点解决多路径枚举与方向性处理问题。
本文介绍在 jgrapht 中查找所有长度恰好为 k、终点为给定顶点的有向路径的多种方法，涵盖内置算法适配技巧与自定义动态规划实现，重点解决多路径枚举与方向性处理问题。
JGraphT 本身不提供开箱即用的“所有长度为 k 的入路径”功能，但可通过巧妙组合现有算法或编写轻量级遍历逻辑高效实现。核心挑战在于：标准最短路径或遍历算法（如 Dijkstra 或 BFS）默认面向“从源出发”，而需求是“汇聚到目标”，且需枚举所有可能路径（而非仅最短一条）。
✅ 推荐方案：反向图 + BFS/DFS 枚举（支持多路径）
最直接可靠的方式是构建原图的反向图（Reverse Graph），然后从目标顶点出发执行受限深度的遍历。JGraphT 提供 AsSubgraph 和 EdgeReversedGraph，推荐使用后者：
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultDirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.builder.GraphBuilder;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.asymmetric.EdgeReversedGraph;
import org.jgrapht.traverse.BreadthFirstIterator;
import org.jgrapht.util.SupplierUtil;
// 构建原始有向图（示例）
Graph<String, DefaultEdge> originalGraph = new DefaultDirectedGraph<>(DefaultEdge.class);
originalGraph.addVertex("A"); originalGraph.addVertex("B"); originalGraph.addVertex("C");
originalGraph.addVertex("D"); originalGraph.addVertex("E"); originalGraph.addVertex("F");
originalGraph.addEdge("A", "B"); originalGraph.addEdge("B", "C");
originalGraph.addEdge("D", "E"); originalGraph.addEdge("E", "C");
originalGraph.addEdge("F", "C");
// 创建反向图：所有边方向翻转 → 入路径变为出路径
Graph<String, DefaultEdge> reversedGraph = new EdgeReversedGraph<>(originalGraph);
// 从目标顶点 C 出发，执行 BFS，限制最大深度为 k=2
String target = "C";
int k = 2;
List<List<String>> allPaths = new ArrayList<>();
Deque<List<String>> queue = new ArrayDeque<>();
// 初始化：路径仅含目标顶点
queue.offer(Arrays.asList(target));
while (!queue.isEmpty()) {
List<String> path = queue.poll();
if (path.size() == k + 1) { // k 条边 → k+1 个顶点
allPaths.add(new ArrayList<>(path));
continue;
}
String last = path.get(path.size() - 1);
// 遍历反向图中从 last 出发的所有邻接顶点（即原图中指向 last 的前驱）
for (String predecessor : reversedGraph.vertexSet()) {
if (reversedGraph.containsEdge(last, predecessor)) {
List<String> newPath = new ArrayList<>(path);
newPath.add(predecessor);
queue.offer(newPath);
}
}
}
// 输出结果：[[C, B, A], [C, E, D]] → 对应原图路径 (A→B→C), (D→E→C)
System.out.println(allPaths.stream()
.map(p -> p.reversed().collect(Collectors.toList()))
.collect(Collectors.toList()));⚠️ 注意：上述 BFS 实现会生成所有路径，但未去重（若存在环需额外判重）。实际应用中建议封装为可复用工具方法，并加入 visited 集合防环。
⚠️ 其他方案对比与局限
Dijkstra + 距离阈值（仅单路径）
如答案所述，DijkstraShortestPath(graph, maxWeight) 可限制搜索半径，但仅返回每起点到目标的最短路径一条，无法满足“所有路径”需求。适用于仅需最优解的场景。Floyd-Warshall + 回溯（高开销）
全源最短路径算法时间复杂度 O(V³)，适合小图且仅需距离判断；但获取具体路径需额外存储前驱矩阵，工程成本高，不推荐用于纯路径枚举。正向 BFS + 深度过滤（低效）
对每个顶点运行 BFS 到目标，再筛选深度为 k 的路径——时间复杂度 O(V·(V+E))，远不如反向图一次遍历高效。
✅ 最佳实践总结
| 场景 | 推荐方法 | 关键要点 |
|---|---|---|
| 需要全部路径（含多条相同长度路径） | 反向图 + DFS/BFS 枚举 | 使用 EdgeReversedGraph，递归/队列控制路径长度，注意环检测 |
| 仅需最短路径且图稀疏 | DijkstraShortestPath + 反向图 | 设置 maxDistance = k，但结果唯一 |
| 顶点数 < 100，需灵活路径约束 | 自定义动态规划 | dp[v][len] = 所有长度为 len 终止于 v 的路径列表，按长度迭代更新 |
最终，反向图遍历是平衡简洁性、正确性与性能的首选。JGraphT 的设计哲学强调组合性而非大而全的 API，理解图的方向性与算法视角转换，是高效使用该库的关键。
