如何修改Dijkstra算法检测带权有向图中多条最短路径

要检测指定节点对之间的多条最短路径，核心是记录每个节点的最短路径数量以及所有可能的前驱节点——原算法仅记录单条路径的前驱，完全无法捕捉多路径场景。下面我会一步步修改你提供的Weiss版本Dijkstra实现：

1. 扩展Vertex类的属性 #

首先给顶点类新增两个关键属性，分别用于统计最短路径总数和存储所有能产生最短路径的前驱节点：

public class Vertex {
    public String name;
    public List<Edge> adj;
    public double dist;
    public Vertex prev;
    public int scratch;
    // 新增：记录到当前节点的最短路径总数
    public int pathCount;
    // 新增：存储所有能产生最短路径的前驱节点
    public List<Vertex> predecessors;

    public Vertex(String name) {
        this.name = name;
        adj = new ArrayList<>();
        dist = Double.POSITIVE_INFINITY;
        prev = null;
        scratch = 0;
        pathCount = 0;
        predecessors = new ArrayList<>();
    }
}

2. 更新clearAll()方法 #

在重置顶点状态时，别忘了清空新增的路径统计属性，避免上次计算的残留数据干扰结果：

private void clearAll() {
    for (Vertex v : vertexMap.values()) {
        v.dist = Double.POSITIVE_INFINITY;
        v.prev = null;
        v.scratch = 0;
        // 新增重置逻辑
        v.pathCount = 0;
        v.predecessors.clear();
    }
}

3. 修改Dijkstra核心逻辑 #

原算法仅处理“找到更短路径”的情况，我们需要新增“找到等长最短路径”的分支，同时调整节点处理判断——原逻辑跳过已处理节点会漏掉后续等长路径的统计，必须优化：

public void dijkstra(String startName) {
    PriorityQueue<Path> pq = new PriorityQueue<>();
    Vertex start = vertexMap.get(startName);
    if (start == null)
        throw new NoSuchElementException("Start vertex not found");

    clearAll();
    pq.add(new Path(start, 0));
    start.dist = 0;
    // 起点到自身的最短路径数默认是1
    start.pathCount = 1;
    int nodesSeen = 0;

    while (!pq.isEmpty() && nodesSeen < vertexMap.size()) {
        Path vrec = pq.remove();
        Vertex v = vrec.dest;

        // 关键修改：如果当前路径长度大于已知最短距离，说明是过时路径，直接跳过
        // 替代原有的"已处理则跳过"逻辑，确保所有有效路径都被处理
        if (vrec.cost > v.dist) {
            continue;
        }

        // 仅第一次处理节点时标记为已处理
        if (v.scratch == 0) {
            v.scratch = 1;
            nodesSeen++;
        }

        for (Edge e : v.adj) {
            Vertex w = e.dest;
            double cvw = e.cost;
            if (cvw < 0)
                throw new GraphException("Graph has negative edges");

            double newDist = v.dist + cvw;
            if (newDist < w.dist) {
                // 情况1：找到更短的路径，重置路径统计信息
                w.dist = newDist;
                w.pathCount = v.pathCount;
                w.predecessors.clear();
                w.predecessors.add(v);
                pq.add(new Path(w, w.dist));
            } else if (newDist == w.dist) {
                // 情况2：找到等长的最短路径，累加路径数并添加前驱
                w.pathCount += v.pathCount;
                if (!w.predecessors.contains(v)) {
                    w.predecessors.add(v);
                }
                // 无需加入队列，因为w的最短距离未发生变化
            }
        }
    }
}

4. 检测指定节点对的多条最短路径 #

修改完成后，要判断起点到目标节点是否存在多条最低成本路径，只需检查两个直观指标：

• 路径总数：如果target.pathCount > 1，说明存在多条不同的最短路径（包括通过不同前驱的路径，以及前驱节点自身的多条路径）。
• 前驱节点数量：如果target.predecessors.size() > 1，说明至少有两条完全不同的路径（通过不同的前驱节点到达目标）。

示例代码：

// 假设已运行dijkstra("StartNode")初始化最短路径
Vertex target = vertexMap.get("TargetNode");
if (target.pathCount > 1) {
    System.out.println("存在多条最低成本路径，总数量为：" + target.pathCount);
} else {
    System.out.println("仅存在一条最低成本路径");
}

关键修改点说明 #

1. 节点处理逻辑优化：原算法跳过已处理节点，会导致后续出现的等长路径无法更新目标节点的统计信息。改为判断当前路径长度是否大于已知最短距离，确保所有有效路径都被处理。
2. 双维度路径统计：通过pathCount统计总路径数，predecessors记录不同的路径分支，既可以判断是否存在多路径，也能追溯具体的路径走向。

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