摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回），所以主要围绕教材的内容学习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的第14回-《第k短路径和EppsteinKShortestPath类》，这回学习的主要内容是：
最短路径
EppsteinKShortestPath类
一、最短路径
GraphPath接口
实现GraphPath接口的对象用于存储路径，也见第6回（包括非简单路径），接口的方法如下：
defaultjava.util.List getEdgeList：返回构成路径的全部边。
V getEndVertex：返回路径中的终点顶点。
defaultintgetLength：返回路径的长度，以边的数量来衡量。
V getStartVertex：返回路径中的起点顶点。
defaultjava.util.List getVertexList：将路径中的顶点序列。
doublegetWeight：返回分配给该路径的权重（路径中边的权重之和）。
二、EppsteinKShortestPath类
JGaphT框架称：大卫・埃普斯坦（David Eppstein）在1999 年给出寻找第 k 短的路径发表在《工业与应用数学学会计算期刊》（SIAM J. Comput.）第 28 卷，第 2 期（1999 年 2 月）第 652 - 673 页。该算法的主要优点在于它能达到 O(m+nlogn+klogk)的时间复杂度，同时保证所生成的k条路径按权重升序排列。其中，m是图中边的数量，n是图中顶点的数量，k是所需路径的数量。此实现仅适用于有向网络简单图。
// 创建 EppsteinKShortestPath 实例
EppsteinKShortestPath eppstein
= new EppsteinKShortestPath<>(graph);
// 获取 k 条最短路径
List> paths =
eppstein.getPaths(source, target, k);
三、代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子14.1 第k短的路径(效果如图14.1)
求下列有向网络的顶点到顶点的第k短路径。
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex14_1.java
C:\studyJGrapht>java -cplib\*;. Ex14_1
图14.1 第k短路径
Ex14_1.java
importorg.jgrapht.Graph;
importorg.jgrapht.GraphPath;
importorg.jgrapht.alg.shortestpath.EppsteinKShortestPath;
importorg.jgrapht.graph.DefaultWeightedEdge;
importorg.jgrapht.graph.SimpleDirectedWeightedGraph;
importjava.util.List;
public classEx14_1{
public static void main(String[] args) {
// 创建一个有向加权简单图
Graph graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
// 添加顶点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
// 添加边并设置权重graph.setEdgeWeight(graph.addEdge("A", "B"), 1);graph.setEdgeWeight(graph.addEdge("B", "C"), 2);graph.setEdgeWeight(graph.addEdge("C", "D"), 3);graph.setEdgeWeight(graph.addEdge("A", "D"), 7);graph.setEdgeWeight(graph.addEdge("A", "C"), 5);// 定义起点、终点和要查找的最短路径数量String source = "A";String target = "D";intk = 3;// 创建 EppsteinKShortestPath 实例EppsteinKShortestPath eppstein = new EppsteinKShortestPath<>(graph);// 获取 k 条最短路径List> paths = eppstein.getPaths(source, target, k);// 输出结果System.out.println( source + " 到 "+ target );if(paths != null) {for(inti = 0; i < paths.size; i++) {GraphPath path = paths.get(i);System.out.println("第 "+ (i + 1) + " 条最短路径: "+ path.getVertexList);System.out.print(path.getEdgeList);//JGraphT的默认格式里是冒号System.out.println("路径权重: "+ path.getWeight);printPath(path);}} else{System.out.println("未找到从 "+ source + " 到 "+ target + " 的路径。");}}// 打印最短路径及其权重的方法public static void printPath(GraphPath shortestPath) {List vertexList = shortestPath.getVertexList;StringBuilder pathStr = new StringBuilder;for(inti = 0; i < vertexList.size; i++) {pathStr.append(vertexList.get(i));if(i < vertexList.size - 1) {pathStr.append(" -> ");}}System.out.println(pathStr + "(路径权重:"+ shortestPath.getWeight+")");}}
