摘要：图图学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的第12回-《最短路径和DijkstraShortestPath类》，这回学习的主要内容是：
GraphPath接口
实现GraphPath接口的对象用于存储路径，也见第6回（包括非简单路径），接口的方法如下：
defaultjava.util.List getEdgeList：返回构成路径的全部边。
V getEndVertex：返回路径中的终点顶点。
defaultintgetLength：返回路径的长度，以边的数量来衡量。
V getStartVertex：返回路径中的起点顶点。
defaultjava.util.List getVertexList：将路径中的顶点序列。
doublegetWeight：返回分配给该路径的权重（路径中边的权重之和）。
二、DijkstraShortestPath类
Dijkstra（狄克斯特拉）算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。JGaphT框架把Dijkstra算法封装在DijkstraShortestPath类中，对于一个有n个节点和m条边的图，迪杰斯特拉算法的时间复杂度为O(m+n^2)。
// 创建 DijkstraShortestPath 实例
DijkstraShortestPaths dijkstra =
new DijkstraShortestPath<>(graph);
// 获取指定顶点对之间的最短路径长度
String source= "A";
String target = "D";
// 获取指定顶点对之间的最短路径
GraphPath shortestPath = dijkstra.getPath(source, target);
if(shortestPath != null) {
System.out.println("从顶点 "+ source+ " 到顶点 "+ target + " 的最短路径是: "+ shortestPath.getVertexList);
} else{
System.out.println("从顶点 "+ source+ " 到顶点 "+ target + " 不存在路径。");
}
三、IntVertexDijkstraShortestPath类
JGraphT在其框架中称：IntVertexDijkstraShortestPath类是专为具有整数顶点的图实现的迪杰斯特拉最短路径算法。当图的顶点编号范围是从 0 到n-1 （其中n 是图的顶点数量）时，这个类避免使用哈希表。如果顶点不在这个范围内，那么会使用开放寻址哈希表（线性探测法）将它们映射到这个范围内。这种实现方式应该比我们更通用的 DijkstraShortestPath 实现更快，因为它避免了对哈希表的大量使用。
JGraphT框架原文：Dijkstra Shortest Path implementation specialized for graphs with integer vertices.This class avoids using hash tables when the vertices are numbered from 0 to n−1 where n is the number of vertices of the graph. If vertices are not in this range, then they are mapped in this range using an open addressing hash table (linear probing).This implementation should be faster than our more generic one which is DijkstraShortestPath since it avoids the extensive use of hash tables.)。
Graph<Integer, DefaultWeightedEdge> graph =
new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
IntVertexDijkstraShortestPath<DefaultWeightedEdge> dijkstra =
new IntVertexDijkstraShortestPath<>(graph);
GraphPath<Integer, DefaultWeightedEdge> shortestPath =
dijkstra.getPath(source, target);
四、代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子12.1 Dijkstra最短路径(效果如图12.1)
求下列有向网络的所有顶点到顶点的最短路径。
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex12_1.java
C:\studyJGrapht>java -cplib\*;. Ex12_1
图12.1 Dijkstra最短路径
Ex12_1.java
importorg.jgrapht.Graph;
importorg.jgrapht.GraphPath;
importorg.jgrapht.alg.shortestpath.DijkstraShortestPath;
importorg.jgrapht.graph.DefaultWeightedEdge;
importorg.jgrapht.graph.SimpleDirectedWeightedGraph;
importjava.util.*;
public classEx12_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"), 12);
graph.setEdgeWeight(graph.addEdge("B", "C"), 1);
graph.setEdgeWeight(graph.addEdge("C", "D"), 3);
graph.setEdgeWeight(graph.addEdge("A", "D"), 10);
graph.setEdgeWeight(graph.addEdge("D", "B"), 1);
// 创建 DijkstraShortestPath实例
DijkstraShortestPath dijkstra = new DijkstraShortestPath<>(graph);
// 获取图的所有顶点
List vertices = new ArrayList<>(graph.vertexSet);
// 遍历每对不同的顶点
for(inti = 0; i < vertices.size; i++) {
for(intj = 0; j < vertices.size; j++) {
if(i != j) {
String source = vertices.get(i);
String target = vertices.get(j);
// 获取指定顶点对之间的最短路径
GraphPath shortestPath = dijkstra.getPath(source, target);
if(shortestPath != null) {
System.out.println(source + " 到 "+ target + " 的最短路径:");
printPath(shortestPath);
System.out.print(shortestPath.getEdgeList);//JGraphT的默认格式里是冒号
System.out.println("(路径权重:"+shortestPath. getWeight+")");
}
}
}
}
}
// 打印最短路径及其权重的方法
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+")");
}
}
例子12.2 int型顶点的Dijkstra最短路径(效果如图12.2)
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex12_2.java
C:\studyJGrapht>java -cplib\*;. Ex12_2
图12.2 int顶点的Dijkstra最短路径
Ex12_2.java
importorg.jgrapht.Graph;
importorg.jgrapht.GraphPath;
importorg.jgrapht.alg.shortestpath.IntVertexDijkstraShortestPath;
importorg.jgrapht.graph.DefaultWeightedEdge;
importorg.jgrapht.graph.SimpleDirectedWeightedGraph;
importjava.util.*;
public classEx12_2{
public static void main(String[] args) {
// 创建一个有向带权图
Graph graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
// 添加顶点
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
// 添加边并设置权重
graph.setEdgeWeight(graph.addEdge(0, 1), 12);
graph.setEdgeWeight(graph.addEdge(1, 2), 1);
graph.setEdgeWeight(graph.addEdge(2, 3), 3);
graph.setEdgeWeight(graph.addEdge(0, 3), 10);
graph.setEdgeWeight(graph.addEdge(3, 1), 1);
// 创建 FloydWarshallShortestPaths 实例
IntVertexDijkstraShortestPath dijkstra =
new IntVertexDijkstraShortestPath<>(graph);
// 获取图的所有顶点
List vertices = new ArrayList<>(graph.vertexSet);
// 遍历每对不同的顶点
for(inti = 0; i < vertices.size; i++) {
for(intj = 0; j < vertices.size; j++) {
if(i != j) {
intsource = vertices.get(i);
inttarget = vertices.get(j);
// 获取指定顶点对之间的最短路径
GraphPath shortestPath = dijkstra.getPath(source, target);
if(shortestPath != null) {
System.out.println(source + " 到 "+ target + " 的最短路径:");
printPath(shortestPath);
System.out.print(shortestPath.getEdgeList);//JGraphT的默认格式里是冒号
System.out.println("(路径权重:"+shortestPath. getWeight+")");
}
}
}
}
}
// 打印最短路径及其权重的方法
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+")");
}
}
