如何修改JGraphT中Dijkstra算法的路径判定标准？

问题背景 #

处理关联游乐园游乐场所的无向图，顶点代表场所，边（Vecinity类）包含distance（距离）和avgTime（平均耗时）属性。当前使用JGraphT的DijkstraShortestPath默认按距离计算最短路径，需修改为支持分别按距离和平均时间两种属性计算。

现有代码：

public static List<Place> exercise2a(Graph<Place,Vecinity> g, Place p1, Place p2) { 
    var alg = new DijkstraShortestPath<Place, Vecinity>(g); 
    return alg.getPath(p1, p2).getVertexList(); 
}

解决方案 #

JGraphT的DijkstraShortestPath支持通过**自定义边权重函数（EdgeWeightFunction）**指定路径权重计算逻辑，无需修改算法核心，仅需在初始化时传入对应权重函数即可。

1. 通用切换实现（推荐） #

封装一个通用方法，通过枚举参数切换权重类型，复用逻辑：

import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.Graph;
import org.jgrapht.alg.util.EdgeWeightFunction;

import java.util.List;

public class AmusementParkPathCalculator {
    // 定义权重类型枚举，清晰区分两种判定依据
    public enum WeightMetric {
        DISTANCE, AVERAGE_TIME
    }

    public static List<Place> getShortestPath(Graph<Place, Vecinity> graph, Place start, Place end, WeightMetric metric) {
        EdgeWeightFunction<Vecinity> weightFunc;
        switch (metric) {
            case DISTANCE:
                // 以边的distance属性作为权重
                weightFunc = edge -> edge.getDistance();
                break;
            case AVERAGE_TIME:
                // 以边的avgTime属性作为权重
                weightFunc = edge -> edge.getAvgTime();
                break;
            default:
                throw new IllegalArgumentException("Unsupported weight metric");
        }

        // 传入自定义权重函数初始化Dijkstra算法
        DijkstraShortestPath<Place, Vecinity> dijkstra = new DijkstraShortestPath<>(graph, weightFunc);
        return dijkstra.getPath(start, end).getVertexList();
    }

    // 快捷方法：按距离计算
    public static List<Place> getShortestPathByDistance(Graph<Place, Vecinity> graph, Place start, Place end) {
        return getShortestPath(graph, start, end, WeightMetric.DISTANCE);
    }

    // 快捷方法：按平均时间计算
    public static List<Place> getShortestPathByAvgTime(Graph<Place, Vecinity> graph, Place start, Place end) {
        return getShortestPath(graph, start, end, WeightMetric.AVERAGE_TIME);
    }
}

2. 独立方法实现（简洁直接） #

如果不需要动态切换，可直接编写两个独立方法，逻辑更直观：

// 按距离计算最短路径
public static List<Place> getShortestPathByDistance(Graph<Place, Vecinity> g, Place p1, Place p2) {
    EdgeWeightFunction<Vecinity> distanceWeight = edge -> edge.getDistance();
    DijkstraShortestPath<Place, Vecinity> alg = new DijkstraShortestPath<>(g, distanceWeight);
    return alg.getPath(p1, p2).getVertexList();
}

// 按平均时间计算最短路径
public static List<Place> getShortestPathByAvgTime(Graph<Place, Vecinity> g, Place p1, Place p2) {
    EdgeWeightFunction<Vecinity> timeWeight = edge -> edge.getAvgTime();
    DijkstraShortestPath<Place, Vecinity> alg = new DijkstraShortestPath<>(g, timeWeight);
    return alg.getPath(p1, p2).getVertexList();
}

关键说明 #

• EdgeWeightFunction是函数式接口，可通过Lambda表达式快速实现，直接从Vecinity边实例中提取目标属性作为权重值。
• 算法会基于权重函数返回的值，计算路径的总权重（总和），最终返回总权重最小的路径。

内容的提问来源于stack exchange，提问作者Aarón Acuña