如何使用JGraphT 1.5.1寻找必经指定顶点的最短路径？

JGraphT 1.5.1版本确实没有ConstrainedShortestPathAlgorithm类，该类是在1.6.0版本才正式加入的。以下提供两种可行解决方案：

方案一：升级JGraphT版本到1.6.0及以上 #

如果项目允许升级依赖，直接使用官方提供的约束最短路径实现即可。调整后的代码如下：

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.shortestpath.ConstrainedShortestPathAlgorithm;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
        // 创建加权图
        Graph<String, DefaultWeightedEdge> graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

        // 添加顶点
        List<String> vertices = Arrays.asList("A", "B", "C", "D", "E", "F");
        vertices.forEach(graph::addVertex);

        // 添加带权重的边
        graph.setEdgeWeight(graph.addEdge("A", "B"), 3);
        graph.setEdgeWeight(graph.addEdge("A", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "E"), 4);
        graph.setEdgeWeight(graph.addEdge("D", "F"), 3);
        graph.setEdgeWeight(graph.addEdge("E", "F"), 2);

        // 设置必须经过的顶点约束
        Set<String> constraints = new HashSet<>(Arrays.asList("B", "D"));

        // 使用官方约束最短路径算法
        ConstrainedShortestPathAlgorithm<String, DefaultWeightedEdge> cspa = 
            new ConstrainedShortestPathAlgorithm<>(graph);
        ConstrainedShortestPathAlgorithm.VertexSetConstraint<String, DefaultWeightedEdge> constraint =
            new ConstrainedShortestPathAlgorithm.VertexSetConstraint<>(constraints);
        GraphPath<String, DefaultWeightedEdge> shortestPath = cspa.getShortestPath("A", "F", constraint);

        // 输出结果
        System.out.println("必须经过顶点 " + constraints + " 的最短路径: " + 
            shortestPath.getVertexList() + ", 总权重=" + shortestPath.getWeight());
    }
}

注意：升级后需确保依赖配置正确，例如Maven依赖需指定1.6.0及以上版本：

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-core</artifactId>
    <version>1.6.0</version>
</dependency>

方案二：在JGraphT 1.5.1中手动实现约束最短路径 #

若无法升级版本，可通过拆分路径+枚举顶点排列的方式手动实现。核心思路是：将"起点→必须经过所有指定顶点→终点"的路径拆分为多段最短路径，枚举所有指定顶点的排列组合，计算每种组合的总路径权重，取最小值。

实现代码如下：

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
import org.jgrapht.util.PermutationGenerator;

import java.util.*;

public class Test {
    public static void main(String[] args) {
        // 创建加权图
        Graph<String, DefaultWeightedEdge> graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);

        // 添加顶点
        List<String> vertices = Arrays.asList("A", "B", "C", "D", "E", "F");
        vertices.forEach(graph::addVertex);

        // 添加带权重的边
        graph.setEdgeWeight(graph.addEdge("A", "B"), 3);
        graph.setEdgeWeight(graph.addEdge("A", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "C"), 1);
        graph.setEdgeWeight(graph.addEdge("B", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "D"), 2);
        graph.setEdgeWeight(graph.addEdge("C", "E"), 4);
        graph.setEdgeWeight(graph.addEdge("D", "F"), 3);
        graph.setEdgeWeight(graph.addEdge("E", "F"), 2);

        String start = "A";
        String end = "F";
        Set<String> requiredVertices = new HashSet<>(Arrays.asList("B", "D"));

        // 获取所有必须经过顶点的排列组合
        List<String> requiredList = new ArrayList<>(requiredVertices);
        PermutationGenerator<String> permGen = new PermutationGenerator<>(requiredList);

        GraphPath<String, DefaultWeightedEdge> bestPath = null;
        double minTotalWeight = Double.MAX_VALUE;

        DijkstraShortestPath<String, DefaultWeightedEdge> dijkstra = new DijkstraShortestPath<>(graph);

        // 遍历每种排列
        while (permGen.hasNext()) {
            List<String> permutation = permGen.next();
            double totalWeight = 0;
            List<String> fullPath = new ArrayList<>();
            fullPath.add(start);
            String current = start;
            boolean valid = true;

            // 计算起点到第一个约束顶点的路径
            for (String vertex : permutation) {
                GraphPath<String, DefaultWeightedEdge> segment = dijkstra.getPath(current, vertex);
                if (segment == null) {
                    valid = false;
                    break;
                }
                totalWeight += segment.getWeight();
                // 拼接路径（去掉重复的起点）
                fullPath.addAll(segment.getVertexList().subList(1, segment.getVertexList().size()));
                current = vertex;
            }

            // 计算最后一个约束顶点到终点的路径
            if (valid) {
                GraphPath<String, DefaultWeightedEdge> finalSegment = dijkstra.getPath(current, end);
                if (finalSegment == null) {
                    continue;
                }
                totalWeight += finalSegment.getWeight();
                fullPath.addAll(finalSegment.getVertexList().subList(1, finalSegment.getVertexList().size()));

                // 更新最优路径
                if (totalWeight < minTotalWeight) {
                    minTotalWeight = totalWeight;
                    // 构建完整的GraphPath对象
                    bestPath = new GraphPath<>(
                        graph,
                        start,
                        end,
                        fullPath,
                        null,
                        totalWeight
                    );
                }
            }
        }

        // 输出结果
        if (bestPath != null) {
            System.out.println("必须经过顶点 " + requiredVertices + " 的最短路径: " + 
                bestPath.getVertexList() + ", 总权重=" + bestPath.getWeight());
        } else {
            System.out.println("不存在满足约束的路径");
        }
    }
}

代码说明 #

• 使用PermutationGenerator生成所有必须经过顶点的排列，确保覆盖所有可能的经过顺序
• 用DijkstraShortestPath计算每段的最短路径，拼接后计算总权重
• 遍历所有排列，筛选出总权重最小的路径作为结果

内容的提问来源于stack exchange，提问作者nohahanon