摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回25个实例），所以主要围绕教材的内容学习JGraphT开源框架，即学JGraphT开源框架中最重要的部分，不是学习JGraphT开源框架的全部内容（JGraphT开源框架封装关于最短路径的算法类就有30多个）。掌握这里的这些内容，也可以让我们在实际项目更加容易地使用图论的算法，这也正是框架的目的。 图图学开源JGraphT开源框架目录如下：
图图学开源JGraphT的第11回-《最短路径和FloydWarshallShortestPaths类》，这回学习的主要内容是：
一、最短路径
GraphPath接口： 实现GraphPath接口的对象用于存储路径，也见第6回（包括非简单路径），接口的方法如下：
defaultjava.util.List getEdgeList：返回构成路径的全部边。
V getEndVertex：返回路径中的终点顶点。
defaultintgetLength：返回路径的长度，以边的数量来衡量。
V getStartVertex：返回路径中的起点顶点。
defaultjava.util.List getVertexList：将路径中的顶点序列。
doublegetWeight：返回分配给该路径的权重（路径中边的权重之和)
二、FloydWarshallShortestPaths类
Floyd 算法封装在FloydWarshallShortestPaths类中，并给出说明：Floyd - Warshall算法能在O(n^3),n的三次方（n是顶点数目）的时间复杂度内找出所有的最短路径（共计n^2 条）。FloydWarshallShortestPaths在构造对象时，不会进行任何计算！所有的计算都在首次调用该类的某个成员方法时进行。计算结果会被存储起来，因此后续对同一方法的所有调用在计算效率上都较高。
// 创建 FloydWarshallShortestPaths 实例
FloydWarshallShortestPaths
floydWarshall = new FloydWarshallShortestPaths<>(graph);
// 获取指定顶点对之间的最短路径长度
String source= "A";
String target = "D";
// 获取指定顶点对之间的最短路径
GraphPath shortestPath = floydWarshall.getPath(source, target);
if(shortestPath != null) {
System.out.println("从顶点 "+ source+ " 到顶点 "+ target + " 的最短路径是: "+ shortestPath.getVertexList);
}
else{
System.out.println("从顶点 "+ source+ " 到顶点 "+ target + " 不存在路径。");
}
四、代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子11.1 floyd最短路径(效果如图11.1)
求下列有向网络的所有顶点到顶点的最短路径。
如下编译和运行代码。
C:\studyJGrapht>javac -cplib\*;. Ex13_1.java
C:\studyJGrapht>java -cplib\*;. Ex13_1
图11.1 floyd最短路径
Ex11_1.java
importorg.jgrapht.Graph;
importorg.jgrapht.GraphPath;
importorg.jgrapht.alg.shortestpath.FloydWarshallShortestPaths;
importorg.jgrapht.graph.DefaultWeightedEdge;
importorg.jgrapht.graph.SimpleDirectedWeightedGraph;
importjava.util.*;
public classEx11_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);
// 创建 FloydWarshallShortestPaths 实例
FloydWarshallShortestPaths floydWarshall = new FloydWarshallShortestPaths<>(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 = floydWarshall.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+")");
}
}
