摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回25个实例），所以主要围绕教材的内容学习JGraphT开源框架，即学JGraphT开源框架中最重要的部分，不是学习JGraphT开源框架的全部内容（JGraphT开源框架封装关于最短路径的算法类就有30多个）。掌握这里的这些内容，也可以让我们在实际项目更加容易地使用图论的算法，这也正是框架的目的。
图图学开源JGraphT开源框架目录如下：
第1回《无向图和SimpleGraph 类》
第2回《Graph 接口》
第3回《无向图和BiconnectivityInspector 类》
第4回《有向图和SimpleDirectedGraph类》
第5回《有向图和GabowStrongConnectivityInspector类》
第6回《有向图与AllDirectedPaths类》
第7回《无向网络和SimpleWeightedGraph 类》
第8回《有向网络和SimpleDirectedWeightedGraph类》
第9回《深度优先搜索（DFS）和DepthFirstIterator类》
第10回《广度优先搜索（BFS）和BreadthFirstIterator类》
第11回《最短路径和FloydWarshallShortestPaths类》
第12回《最短路径和DijkstraShortestPath类》
第13回《最短路径和BFSShortestPath类》
第14回《第k短路径和EppsteinKShortestPath类》
第15回《最小生成树和PrimMinimumSpanningTree类》
第16回《拓扑排序和TopologicalOrderIterator类》
第17回《图着色与GreedyColoring类》
第18回《介数和Betweenness Centrality类》
第19回《最大流算法和EdmondsKarpMFImpl类》
这是
图图学开源JGraphT的第6回-《有向图与AllDirectedPaths类》，这回学习的主要内容是：
GraphPath接口
AllDirectedPaths类
例子6.1 给出有向图的简单路径
一、GraphPath接口
实现GraphPath接口的对象用于存储路径（包括非简单路径），接口的方法如下：
defaultjava.util.List getEdgeList：返回构成路径的全部边。
V getEndVertex：返回路径中的终点顶点。
defaultintgetLength：返回路径的长度，以边的数量来衡量。
V getStartVertex：返回路径中的起点顶点。
defaultjava.util.List getVertexList：将路径中的顶点序列。
doublegetWeight：返回分配给该路径的权重（路径中边的权重之和）。
二、AllDirectedPaths类
AllDirectedPaths类的实例可用于获取有向图中两个顶点之间的路径，例如：
//创建 AllDirectedPaths 实例
AllDirectedPaths<String, DefaultEdge>allDirectedPaths =
newAllDirectedPaths<>(directedGraph);
//指定源顶点和目标顶点
String sourceVertex ="A";
String targetVertex ="D";
//只计算简单路径，最大路径长度为 3（是路径的自然长度）
booleansimplePathsOnly =true;
IntegermaxPathLength =3;
//调用 getAllPaths 方法获取所有路径
List<GraphPath<String, DefaultEdge>>paths =
allDirectedPaths.getAllPaths(sourceVertex, targetVertex, simplePathsOnly, maxPathLength);
三、AllDirectedPaths类的算法特点 JGraphT声称AllDirectedPaths类的算法类似 Dijkstra 的算法，但不是Dijkstra 的算法，说它类似 Dijkstra 算法，可能是因为在搜索路径的过程中采用了一些与 Dijkstra 算法相似的思想，比如对节点的扩展和路径的探索。但本质上，它的目的和 Dijkstra 算法不同，Dijkstra 算法是为了找最短路径，而 AllDirectedPaths 是为了找所有路径，包括简单路径。在图论中，计算出从一个顶点到另一个顶点的所有简单路径，然后选取权重最小的路径，在理论上确实可以得到这两个顶点之间的最短路径。不过，这种方法在实际应用中存在明显的局限性：
时间复杂度高：计算所有简单路径的过程可能会非常耗时，尤其是在大规模图中，因为简单路径的数量可能会随着图的规模呈指数级增长。
空间复杂度高：存储所有简单路径需要大量的内存空间可能会导致内存溢出。
相比之下， Dijkstra 经典最短路径算法具有更高效的时间和空间复杂度，能够在更短的时间内找到最短路径（见后续的内容）。
当一个有向图中的路径不是很复杂时，AllDirectedPaths类可用于在多个路径中选择某条路径，而不是了寻找最短路径，比如，从某地达到另外一个地方，可能有高速（距离最短路径）和国道，但国道费用较低，用户考虑到费用，可能选择国道。
四、 代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子6.1 给出有向图的简单路径(效果如图6.1)
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex6_1.java
C:\studyJGrapht>java -cplib\*;. Ex6_1
图6.1 有向图的简单路径
Ex6_1.java
importorg.jgrapht.Graph;
importorg.jgrapht.alg.shortestpath.AllDirectedPaths;
importorg.jgrapht.graph.DefaultEdge;
importorg.jgrapht.graph.SimpleDirectedGraph;
importorg.jgrapht.GraphPath;
importjava.util.*;
importjava.util.stream.Collectors;
public classEx6_1{
public static void main(String[] args) {
// 创建一个简单有向图
Graph directedGraph = new SimpleDirectedGraph<>(DefaultEdge.class);
// 添加顶点
directedGraph.addVertex("A");
directedGraph.addVertex("B");
directedGraph.addVertex("C");
directedGraph.addVertex("D");
// 添加边
directedGraph.addEdge("A", "B");
directedGraph.addEdge("B", "C");
directedGraph.addEdge("C", "D");
directedGraph.addEdge("A", "C");
// 创建 AllDirectedPaths 实例
AllDirectedPaths allDirectedPaths = new AllDirectedPaths<>(directedGraph);
// 指定源顶点和目标顶点
String sourceVertex = "A";
String targetVertex = "D";
// 只计算简单路径，最大路径长度为 3(自然长度，即路径中边的数目)
boolean simplePathsOnly = true;
Integer maxPathLength = 3;
// 调用 getAllPaths 方法获取所有路径
List> paths = allDirectedPaths.getAllPaths(sourceVertex, targetVertex, simplePathsOnly, maxPathLength);
// 输出所有路径
System.out.println("从顶点 "+ sourceVertex + " 到顶点 "+ targetVertex + " 的所有路径：");
for(GraphPath path : paths) {
System.out.println(path.getVertexList);
}
for(GraphPath path : paths) {
System.out.println(path.getEdgeList);
System.out.println("此路径的权重（路径边的权重和）："+path. getWeight);
}
System.out.println("再来一种输出方法(为了练习方法)：");
for(GraphPath path : paths) {
List vertexList = path.getVertexList;
StringBuffer pathStr = new StringBuffer;
for(inti = 0; i < vertexList.size; i++) {
pathStr.append(vertexList.get(i));
if(i < vertexList.size - 1) {
pathStr.append("->");
}
}
List edgeList = path.getEdgeList;
double sum= 0;
for(DefaultEdge edge : edgeList) {
sum+= directedGraph.getEdgeWeight(edge);
}
System.out.println("路径: "+ pathStr + ", 总权重: "+ sum);
}
}
}
