使用JGrapht在有向边权重图中寻找负圈

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.cycle.CycleDetector;
import org.jgrapht.alg.shortestpath.BellmanFordShortestPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;

public class NegativeCycleFinder {
    public static void main(String[] args) {
        // 创建有向边权重图
        Graph<String, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<>(DefaultWeightedEdge.class);

        // 添加顶点
        graph.addVertex("A");
        graph.addVertex("B");
        graph.addVertex("C");

        // 添加边并设置权重
        DefaultWeightedEdge edge1 = graph.addEdge("A", "B");
        graph.setEdgeWeight(edge1, -2);

        DefaultWeightedEdge edge2 = graph.addEdge("B", "C");
        graph.setEdgeWeight(edge2, 3);

        DefaultWeightedEdge edge3 = graph.addEdge("C", "A");
        graph.setEdgeWeight(edge3, -4);

        // 使用Bellman-Ford算法寻找负圈
        BellmanFordShortestPath<String, DefaultWeightedEdge> bellmanFord = new BellmanFordShortestPath<>(graph);
        GraphPath<String, DefaultWeightedEdge> negativeCycle = bellmanFord.getNegativeCycle();

        // 处理负圈
        if (negativeCycle != null) {
            System.out.println("找到负圈：");
            System.out.println(negativeCycle.getVertexList());
            System.out.println(negativeCycle.getEdgeList());
        } else {
            System.out.println("未找到负圈。");
        }
    }
}