Java使用JGraphT的Dijkstra算法、Bellman-Ford算法求最短路径
JGraphT是一个用Java实现的图论库，提供了用于构建、操作和分析各种类型的图的数据结构和算法。它支持多种类型的图，包括有向图、无向图、加权图等，并提供了许多常用算法的实现，如Dijkstra算法、Bellman-Ford算法、Kruskal算法、Prim算法等。
Maven坐标：
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.0</version>
</dependency>
上面是JGraphT核心模块的Maven坐标，可以将其添加到项目的pom.xml文件中。
接下来我们将实现一个使用JGraphT的Dijkstra算法和Bellman-Ford算法求最短路径的样例，并给出完整的Java代码。
import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm;
import org.jgrapht.alg.shortestpath.BellmanFordShortestPath;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultEdge;
import java.util.List;
public class ShortestPathExample {
public static void main(String[] args) {
// 创建有向加权图
Graph<String, DefaultEdge> graph = new DefaultDirectedWeightedGraph<>(DefaultEdge.class);
// 添加图的顶点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
// 添加图的边和权重
graph.addEdge("A", "B");
graph.setEdgeWeight("A", "B", 1);
graph.addEdge("A", "C");
graph.setEdgeWeight("A", "C", 4);
graph.addEdge("B", "C");
graph.setEdgeWeight("B", "C", 2);
graph.addEdge("B", "D");
graph.setEdgeWeight("B", "D", 5);
graph.addEdge("C", "D");
graph.setEdgeWeight("C", "D", 1);
graph.addEdge("D", "E");
graph.setEdgeWeight("D", "E", 3);
// 使用Dijkstra算法求最短路径
ShortestPathAlgorithm<String, DefaultEdge> dijkstra = new DijkstraShortestPath<>(graph);
GraphPath<String, DefaultEdge> shortestPathDijkstra = dijkstra.getPath("A", "E");
List<String> vertexListDijkstra = shortestPathDijkstra.getVertexList();
double weightDijkstra = shortestPathDijkstra.getWeight();
System.out.println("Dijkstra最短路径: " + vertexListDijkstra);
System.out.println("Dijkstra最短路径权重: " + weightDijkstra);
// 使用Bellman-Ford算法求最短路径
ShortestPathAlgorithm<String, DefaultEdge> bellmanFord = new BellmanFordShortestPath<>(graph);
GraphPath<String, DefaultEdge> shortestPathBellmanFord = bellmanFord.getPath("A", "E");
List<String> vertexListBellmanFord = shortestPathBellmanFord.getVertexList();
double weightBellmanFord = shortestPathBellmanFord.getWeight();
System.out.println("Bellman-Ford最短路径: " + vertexListBellmanFord);
System.out.println("Bellman-Ford最短路径权重: " + weightBellmanFord);
}
}
上面的代码首先创建了一个有向加权图，然后利用图的addVertex方法添加图的顶点，利用graph.addEdge方法和graph.setEdgeWeight方法添加图的边和权重。
接下来，我们使用Dijkstra算法和Bellman-Ford算法分别求最短路径。通过创建相应的算法对象（DijkstraShortestPath和BellmanFordShortestPath），并调用getPath方法，我们可以得到两种算法求得的最短路径，然后分别打印出最短路径和最短路径的权重。
最后，我们得到的输出示例为：
Dijkstra最短路径: [A, B, C, D, E]
Dijkstra最短路径权重: 9.0
Bellman-Ford最短路径: [A, B, C, D, E]
Bellman-Ford最短路径权重: 9.0
可以看到，通过使用JGraphT库提供的Dijkstra算法和Bellman-Ford算法，我们可以轻松地求解有向加权图的最短路径。
总结：JGraphT是一个功能强大的图论库，提供了丰富的数据结构和算法。它可以帮助开发人员快速实现和应用图论相关的算法，如最短路径算法。本示例中，我们展示了如何使用JGraphT的Dijkstra算法和Bellman-Ford算法求解最短路径，并给出了完整的Java代码。
