JGraphT有向无环图(DAG)中单一边分配多权重的可行方案咨询

问题背景 #

需要在表示城市间旅行时间的图中，为每条边同时存储飞机、驾车、公交等多种出行方式的耗时权重，且能针对指定方式查找最短路径，要求方案适用于大型图、支持多线程，同时尽量少修改JGraphT现有代码。

你已尝试的思路存在的问题：

• 为每种出行方式创建独立图：操作繁琐且内存占用过高
• 扩展图类并自定义带参数的getEdgeWeight()：需同步修改所有依赖该方法的算法类，实现成本高
• 通过setWeightMode()切换权重：无法支持多线程场景

推荐方案：自定义边类 + 权重函数传递给算法 #

这是贴合JGraphT设计理念、无需修改核心类、天然支持多线程的最优方案，具体步骤如下：

1. 自定义包含多权重的边类 #

创建一个自定义边类，封装所有需要的权重字段：

public class MultiWeightEdge {
    private double planeTime;
    private double driveTime;
    private double busTime;

    // 构造方法
    public MultiWeightEdge(double plane, double drive, double bus) {
        this.planeTime = plane;
        this.driveTime = drive;
        this.busTime = bus;
    }

    // Getter方法
    public double getPlaneTime() { return planeTime; }
    public double getDriveTime() { return driveTime; }
    public double getBusTime() { return busTime; }

    // 若使用非伪图类型，需重写equals和hashCode确保边的唯一性
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MultiWeightEdge that = (MultiWeightEdge) o;
        return Double.compare(that.planeTime, planeTime) == 0 &&
               Double.compare(that.driveTime, driveTime) == 0 &&
               Double.compare(that.busTime, busTime) == 0;
    }

    @Override
    public int hashCode() {
        return Objects.hash(planeTime, driveTime, busTime);
    }
}

随后用该类作为图的边类型，例如使用DirectedWeightedPseudograph<V, MultiWeightEdge>。

2. 为每种出行方式定义权重函数 #

JGraphT的多数加权算法（如DijkstraShortestPath）支持传入自定义WeightFunction，无需修改算法本身。为每种出行方式实现对应的权重函数：

// 飞机耗时权重函数
WeightFunction<MultiWeightEdge> planeWeightFunc = edge -> edge.getPlaneTime();
// 驾车耗时权重函数
WeightFunction<MultiWeightEdge> driveWeightFunc = edge -> edge.getDriveTime();
// 公交耗时权重函数
WeightFunction<MultiWeightEdge> busWeightFunc = edge -> edge.getBusTime();

3. 调用算法时传入对应权重函数 #

以DijkstraShortestPath为例，调用静态方法时传入目标权重函数即可：

// 查找城市A到城市B的最短飞机路径
GraphPath<V, MultiWeightEdge> planePath = DijkstraShortestPath.findPathBetween(
    graph, planeWeightFunc, cityA, cityB
);

// 查找最短驾车路径
GraphPath<V, MultiWeightEdge> drivePath = DijkstraShortestPath.findPathBetween(
    graph, driveWeightFunc, cityA, cityB
);

方案优势 #

• 内存高效：仅维护一个图实例，所有权重存储在边对象中，避免重复存储顶点与边结构
• 线程安全：每个线程可独立使用不同权重函数调用算法，无共享状态切换问题
• 低侵入性：完全基于JGraphT原生扩展点实现，无需修改核心代码，版本兼容性强
• 扩展性好：新增出行方式仅需在MultiWeightEdge中添加字段并新增对应权重函数，无需改动其他逻辑

注意事项 #

• 若使用其他加权算法（如最小生成树），可检查其是否支持传入自定义WeightFunction，JGraphT多数加权算法均提供此类重载方法
• 若使用非伪图类型（如DirectedWeightedGraph），需确保自定义边类正确实现equals和hashCode方法，保证边的唯一性

内容的提问来源于stack exchange，提问作者LJ in NJ