Dijkstra最短路径算法异常：部分场景仅返回目标节点问题排查

DevOps 小满

2026-7-25

问题：Dijkstra算法实现中路径构建异常，部分场景仅返回目标节点

我实现的基于Dijkstra算法的GraphShortestPath类用于查找最短路径，部分场景下无法正确构建路径：将目标节点加入路径列表后，执行node = predecessors.get(node)时，本该存在前驱节点却返回null，最终仅返回目标节点。

核心实现代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Edge;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Graph;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Node;

public class GraphShortestPath implements PathFinder {
    private Graph graph;
    Map<Node, Double> distances = new HashMap<>(); // tentative distances from start node to each node
    Map<Node, Node> predecessors = new HashMap<>(); // predecessors of each node in the shortest path
    
    public GraphShortestPath(Graph graph) {
        this.graph = graph;
    }
    
    @Override
    public List<Node> findPath(Node start, Node end) {
        

        PriorityQueue<Node> unvisitedNodes = new PriorityQueue<>(Comparator.comparingDouble(distances::get)); // nodes not visited yet
        Set<Node> visitedNodes = new HashSet<>(); // visited nodes
        
        // initialize tentative distances and add all nodes to unvisited nodes
        for (Node node : graph.getNodesList()) {
            if (node.equals(start)) {
                distances.put(node, 0.0);
            } else {
                distances.put(node, Double.POSITIVE_INFINITY);
            }
            unvisitedNodes.offer(node);
        }
        
        // loop until we reach the end node or there are no more nodes to visit
        while (!unvisitedNodes.isEmpty()) {
            Node current = unvisitedNodes.poll();
            
            
            if (current.equals(end)) {

                // we have found the shortest path, reconstruct it using predecessors and return it
                List<Node> shortestPath = new ArrayList<>();
                Node node = end;
                System.out.println(predecessors.size());
                System.out.println();
                while (node != null) {
                    System.out.println(node.getId());
                    shortestPath.add(0, node);
                    node = predecessors.get(node);
                    
                }
                return shortestPath;
            }
            visitedNodes.add(current);
            for (Edge edge : current.getOutEdges()) {
                Node neighbor = edge.getDestination();
                if (visitedNodes.contains(neighbor)) {
                    continue;
                }
                double tentativeDistance = distances.get(current) + edge.getWeight();
                if (tentativeDistance < distances.get(neighbor)) {
                    distances.put(neighbor, tentativeDistance);
                    predecessors.put(neighbor, current);
                    unvisitedNodes.remove(neighbor);
                    unvisitedNodes.offer(neighbor);
                }
            }
        }
        
        // end node is not reachable from start node
        System.out.println("no path was found");
        return null;
    }
}

测试代码（可正常运行）

import java.util.List;

import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Graph;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Node;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.path.GraphShortestPath;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.path.PathFinder;

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();

        graph.addNode(0);
        graph.addNode(1);
        graph.addNode(2);
        graph.addNode(3);
        graph.addNode(4);
        graph.addNode(5);
        graph.addNode(6);
        graph.addNode(7);
        graph.addNode(8);
        graph.addNode(9);
        graph.addNode(10);
        graph.addNode(11);
        graph.addNode(12);
        graph.addNode(13);
        graph.addNode(14);
        graph.addNode(15);
        graph.addNode(16);
        graph.addNode(17);
        graph.addNode(18);
        graph.addNode(19);
        graph.addNode(20);
        
        graph.addEdge(graph.getNode(0), graph.getNode(1));
        graph.addEdge(graph.getNode(0), graph.getNode(7));

        graph.addEdge(graph.getNode(1), graph.getNode(0));
        graph.addEdge(graph.getNode(1), graph.getNode(7));
        graph.addEdge(graph.getNode(1), graph.getNode(2));
        graph.addEdge(graph.getNode(1), graph.getNode(8));

        graph.addEdge(graph.getNode(2), graph.getNode(1));
        graph.addEdge(graph.getNode(2), graph.getNode(8));
        graph.addEdge(graph.getNode(2), graph.getNode(9));
        graph.addEdge(graph.getNode(2), graph.getNode(3));

        graph.addEdge(graph.getNode(3), graph.getNode(2));
        graph.addEdge(graph.getNode(3), graph.getNode(9));
        graph.addEdge(graph.getNode(3), graph.getNode(4));
        graph.addEdge(graph.getNode(3), graph.getNode(10));

        graph.addEdge(graph.getNode(4), graph.getNode(3));
        graph.addEdge(graph.getNode(4), graph.getNode(10));
        graph.addEdge(graph.getNode(4), graph.getNode(11));
        graph.addEdge(graph.getNode(4), graph.getNode(5));

        graph.addEdge(graph.getNode(5), graph.getNode(4));
        graph.addEdge(graph.getNode(5), graph.getNode(11));
        graph.addEdge(graph.getNode(5), graph.getNode(12));
        graph.addEdge(graph.getNode(5), graph.getNode(6));

        graph.addEdge(graph.getNode(6), graph.getNode(5));
        graph.addEdge(graph.getNode(6), graph.getNode(12));

        graph.addEdge(graph.getNode(8), graph.getNode(1));
        graph.addEdge(graph.getNode(8), graph.getNode(2));
        graph.addEdge(graph.getNode(8), graph.getNode(9));
        graph.addEdge(graph.getNode(8), graph.getNode(16));
        graph.addEdge(graph.getNode(8), graph.getNode(15));
        graph.addEdge(graph.getNode(8), graph.getNode(14));
        graph.addEdge(graph.getNode(8), graph.getNode(7));

        PathFinder path = new GraphShortestPath(graph);
        List<Node> l = path.findPath(graph.getNode(0), graph.getNode(6));

        for(Node n: l){
            System.out.println(n.getId());
        }
    }
}

修复方案

1. 核心问题定位

成员变量复用污染：distances和predecessors是类成员变量，多次调用findPath时会保留上一次的计算结果，导致节点的距离和前驱关系被错误覆盖。
优先队列初始化时机错误：在distances未完成所有节点初始化时就创建优先队列，Comparator引用空的distances存在潜在逻辑风险。
Node类匹配逻辑缺失：如果Node未正确实现equals和hashCode，会导致HashMap/HashSet中节点匹配失败，前驱关系无法正确存储和读取。

2. 具体修复步骤

（1）将距离和前驱Map改为方法局部变量

每次调用findPath时重新初始化，避免旧数据干扰：

@Override
public List<Node> findPath(Node start, Node end) {
    Map<Node, Double> distances = new HashMap<>();
    Map<Node, Node> predecessors = new HashMap<>();
    // 后续逻辑不变
}

（2）调整优先队列初始化顺序

先完成所有节点的距离初始化，再创建优先队列：

// 先初始化所有节点距离
for (Node node : graph.getNodesList()) {
    distances.put(node, node.equals(start) ? 0.0 : Double.POSITIVE_INFINITY);
}
// 再创建并填充优先队列
PriorityQueue<Node> unvisitedNodes = new PriorityQueue<>(Comparator.comparingDouble(distances::get));
unvisitedNodes.addAll(graph.getNodesList());

（3）确保Node类实现equals和hashCode

基于节点ID实现匹配逻辑，保证HashMap能正确存储和查找节点：

public class Node {
    private int id;
    // 其他字段和方法
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return id == node.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

（4）补充不可达节点的跳过逻辑

当当前节点距离为无穷大时，说明后续节点都不可达，直接终止循环：

if (distances.get(current) == Double.POSITIVE_INFINITY) {
    break;
}

3. 修复后的完整核心代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Objects;

import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Edge;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Graph;
import ca.mcmaster.cas.se2aa4.a4.pathfinder.graph.Node;

public class GraphShortestPath implements PathFinder {
    private Graph graph;
    
    public GraphShortestPath(Graph graph) {
        this.graph = graph;
    }
    
    @Override
    public List<Node> findPath(Node start, Node end) {
        Map<Node, Double> distances = new HashMap<>();
        Map<Node, Node> predecessors = new HashMap<>();
        Set<Node> visitedNodes = new HashSet<>();
        
        // 初始化所有节点的距离
        for (Node node : graph.getNodesList()) {
            distances.put(node, node.equals(start) ? 0.0 : Double.POSITIVE_INFINITY);
        }
        
        // 初始化优先队列
        PriorityQueue<Node> unvisitedNodes = new PriorityQueue<>(Comparator.comparingDouble(distances::get));
        unvisitedNodes.addAll(graph.getNodesList());
        
        while (!unvisitedNodes.isEmpty()) {
            Node current = unvisitedNodes.poll();
            
            if (current.equals(end)) {
                List<Node> shortestPath = new ArrayList<>();
                Node node = end;
                while (node != null) {
                    shortestPath.add(0, node);
                    node = predecessors.get(node);
                }
                return shortestPath;
            }
            
            // 跳过不可达节点
            if (distances.get(current) == Double.POSITIVE_INFINITY) {
                break;
            }
            
            visitedNodes.add(current);
            for (Edge edge : current.getOutEdges()) {
                Node neighbor = edge.getDestination();
                if (visitedNodes.contains(neighbor)) {
                    continue;
                }
                
                double tentativeDistance = distances.get(current) + edge.getWeight();
                if (tentativeDistance < distances.get(neighbor)) {
                    distances.put(neighbor, tentativeDistance);
                    predecessors.put(neighbor, current);
                    unvisitedNodes.remove(neighbor);
                    unvisitedNodes.offer(neighbor);
                }
            }
        }
        
        System.out.println("未找到路径");
        return null;
    }
}

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

Dijkstra最短路径算法异常：部分场景仅返回目标节点问题排查

核心实现代码 #

测试代码（可正常运行） #

修复方案 #

1. 核心问题定位 #

2. 具体修复步骤 #