基于优先队列的Dijkstra算法Java实现问题求助

Hey there! Let's walk through fixing your Dijkstra implementation step by step, and also add the path tracking functionality you need. Here are the key issues in your current code, plus solutions:

Key Issues in Your Current Implementation #

• Incorrect Priority Queue Ordering: Your PriorityQueue<Intersection> uses the default comparator for Intersection, which doesn't sort nodes by their current distance from the source. This means you're not extracting the node with the smallest distance each time—breaking the core of Dijkstra's algorithm.
• Reversed Relaxation Condition: You wrote if(u.getDistanceFromSource() > v.getDistanceFromSource() + weight) which is backwards. The correct condition checks if going through u gives a shorter path to v: if(v.getDistanceFromSource() > u.getDistanceFromSource() + weight).
• Missing Initialization: You only set the source node's distance to 0, but all other nodes should start with an infinite distance (like Double.POSITIVE_INFINITY). Without this, uninitialized distances might default to 0, leading to incorrect path calculations.
• No Visited/Processed Check: You're reprocessing nodes every time they're added to the priority queue, which wastes computation. Once a node is extracted from the queue (i.e., we've found its shortest path), we shouldn't process it again.
• No Path Tracking: You don't store predecessor nodes, so you can't reconstruct the shortest path from source to destination.

Fixed Implementation with Path Tracking #

First, update your Intersection class to add a predecessor reference and ensure proper distance initialization:

class Intersection {
    String label;
    double distanceFromSource;
    Intersection predecessor; // To track path
    List<Intersection> neighbours;

    public Intersection(String label) {
        this.label = label;
        this.distanceFromSource = Double.POSITIVE_INFINITY;
        this.predecessor = null;
        this.neighbours = new ArrayList<>();
    }

    // Getters and setters for all fields
    public double getDistanceFromSource() { return distanceFromSource; }
    public void setDistanceFromSource(double distance) { this.distanceFromSource = distance; }
    public Intersection getPredecessor() { return predecessor; }
    public void setPredecessor(Intersection predecessor) { this.predecessor = predecessor; }
    public List<Intersection> getNeigbours() { return neighbours; }
}

Now, here's the corrected route function, including path reconstruction:

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

public ArrayList<Intersection> route(String wholeLine){
    String[] temp = wholeLine.split(" |\\>");
    int vel = Integer.parseInt(temp[3]);
    
    // Get source and destination nodes
    Intersection src = intersections.get(temp[1]);
    Intersection dest = intersections.get(temp[2]);

    // Reset all nodes' distance and predecessor (critical for repeated function calls)
    for(Intersection node : intersections.values()){
        node.setDistanceFromSource(Double.POSITIVE_INFINITY);
        node.setPredecessor(null);
    }

    // Priority Queue: sort nodes by their current distance from source (smallest first)
    PriorityQueue<Intersection> pq = new PriorityQueue<>((a, b) -> Double.compare(a.getDistanceFromSource(), b.getDistanceFromSource()));

    // Initialize source node
    src.setDistanceFromSource(0);
    pq.add(src);

    // Track processed nodes to avoid reprocessing (optimization)
    Set<Intersection> processed = new HashSet<>();

    while(!pq.isEmpty()){
        Intersection u = pq.poll();

        // Skip if we've already found the shortest path to this node
        if(processed.contains(u)) continue;
        processed.add(u);

        // Early exit if we reach the destination (optional but efficient)
        if(u.equals(dest)) break;

        // Iterate over all neighbours of u
        for(Intersection v : u.getNeigbours()){
            if(processed.contains(v)) continue; // Skip processed neighbours

            // Find the weight of the edge between u and v
            double weight = 0;
            for(Rail rail : railList){
                boolean isDirectEdge = rail.getSrc().getLabel().equals(u.label) && rail.getDest().getLabel().equals(v.label);
                boolean isReverseEdge = rail.getSrc().getLabel().equals(v.label) && rail.getDest().getLabel().equals(u.label);
                if(isDirectEdge || isReverseEdge){
                    weight = rail.getDistance();
                    break; // Stop searching once we find the correct rail
                }
            }

            // Relaxation step: check if path through u is shorter for v
            if(v.getDistanceFromSource() > u.getDistanceFromSource() + weight){
                v.setDistanceFromSource(u.getDistanceFromSource() + weight);
                v.setPredecessor(u); // Record predecessor to reconstruct path later
                pq.add(v);
            }
        }
    }

    // Reconstruct the shortest path from destination back to source
    ArrayList<Intersection> shortestPath = new ArrayList<>();
    Intersection currentNode = dest;
    while(currentNode != null){
        shortestPath.add(currentNode);
        currentNode = currentNode.getPredecessor();
    }
    // Reverse to get path from source to destination
    Collections.reverse(shortestPath);

    // Handle case where no valid path exists
    if(shortestPath.size() == 1 && !shortestPath.get(0).equals(src)){
        return new ArrayList<>(); // Return empty list if no path found
    }

    return shortestPath;
}

Key Improvements Explained #

1. Priority Queue Comparator: The lambda (a, b) -> Double.compare(a.getDistanceFromSource(), b.getDistanceFromSource()) ensures the queue always extracts the node with the smallest current distance, which is essential for Dijkstra's algorithm.
2. Proper Relaxation Logic: The corrected condition checks if the path through u provides a shorter route to v, updating both the distance and predecessor reference when true.
3. Node Reset: We reset all nodes' distance and predecessor before running the algorithm, which ensures correct results if the route function is called multiple times.
4. Processed Set: This prevents reprocessing nodes once their shortest path is confirmed, reducing unnecessary computations.
5. Path Reconstruction: By tracking each node's predecessor, we backtrack from the destination to the source, then reverse the list to get the path in the correct source-to-destination order.

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