耿老师教你学Java：图图学JGraphT开源框架第11回_科学探索

耿老师教你学Java：图图学JGraphT开源框架第11回

创始人

2025-03-09 11:13:08

摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回25个实例），所以主要围绕教材的内容学习JGraphT开源框架，即学JGraphT开源框架中最重要的部分，不是学习JGraphT开源框架的全部内容（JGraphT开源框架封装关于最短路径的算法类就有30多个）。掌握这里的这些内容，也可以让我们在实际项目更加容易地使用图论的算法，这也正是框架的目的。图图学开源JGraphT开源框架目录如下：

图图学开源JGraphT的第11回-《最短路径和FloydWarshallShortestPaths类》，这回学习的主要内容是：

最短路径
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+")"); } }

Java 算法顶点 -java 路径 Floyd JGraphT 图图框架 target 权重 source graph

⚠️

本网站信息内容及素材来源于网络采集或用户发布，如涉及侵权，请及时联系我们，发送链接至2697952338@QQ.COM，我们将第一时间进行核实与删除处理。

上一篇：如何解决CentOS中／dev／shm共享内存相关问题？

下一篇：中科院院士丁洪倡议发起中学 AI 奥赛

耿老师教你学Java：图图学JGraphT开源框架第11回

相关内容

热门资讯