Java实现最短路径：Dijkstra算法代码报错求助

Hey there! Let's dig into that bug in your Dijkstra algorithm's computePaths() method, specifically the for(Edge e: u.adjacencies) loop. I’ve run into similar snags before, so let’s break this down step by step.

First, most issues here stem from missing or incorrect definitions for the Node/Edge classes, or a misimplemented relaxation logic in the loop. Let's start with the basics.

Step 1: Ensure Your Node and Edge Classes Are Correct #

If your Edge class lacks core properties (like a target node and weight), or your Node's adjacency list isn’t initialized, you’ll hit errors when iterating over u.adjacencies. Here’s the standard, working definition for these classes:

class Node implements Comparable<Node> {
    public final String name;
    public List<Edge> adjacencies;
    public double shortestDistance = Double.POSITIVE_INFINITY;
    public Node predecessor;

    public Node(String name) {
        this.name = name;
        // Critical: Initialize the list to avoid NullPointerExceptions
        this.adjacencies = new ArrayList<>();
    }

    @Override
    public int compareTo(Node other) {
        // Required for PriorityQueue ordering by shortest distance
        return Double.compare(this.shortestDistance, other.shortestDistance);
    }
}

class Edge {
    public final Node target;
    public final double weight;

    public Edge(Node target, double weight) {
        this.target = target;
        this.weight = weight;
    }
}

Step 2: Fix the computePaths() Loop Logic #

Your original code cuts off mid-while loop, so let’s fill in the gaps and correct common mistakes in the edge iteration. The key fix here is implementing the proper relaxation step (updating shortest paths for adjacent nodes):

public static void computePaths(Node source) {
    source.shortestDistance = 0;
    PriorityQueue<Node> queue = new PriorityQueue<>();
    queue.add(source);

    while (!queue.isEmpty()) {
        Node u = queue.poll();

        // Iterate through all adjacent edges of the current node
        for (Edge e : u.adjacencies) {
            Node v = e.target;
            double edgeWeight = e.weight;
            double newDistance = u.shortestDistance + edgeWeight;

            // Relaxation check: if we found a shorter path to v through u
            if (newDistance < v.shortestDistance) {
                // Java's PriorityQueue doesn't auto-update, so remove old entry if present
                queue.remove(v);
                // Update the node's shortest distance and predecessor
                v.shortestDistance = newDistance;
                v.predecessor = u;
                // Re-add the updated node to the queue
                queue.add(v);
            }
        }
    }
}

Common Mistakes to Double-Check #

Let’s cover the errors that usually pop up here:

• NullPointerException on u.adjacencies: You forgot to initialize the adjacency list in the Node constructor. Always set it to a new ArrayList<>() when creating a Node.
• Missing Edge Properties: If your Edge class doesn’t have target or weight fields, the loop can’t access those values. Verify your Edge class definition.
• Backwards Relaxation Logic: Writing newDistance > v.shortestDistance instead of < will update paths to be longer instead of shorter—this breaks the entire algorithm.
• Ignoring Priority Queue Updates: When you update a node’s shortest distance, you need to re-add it to the queue (or remove the old entry first) because Java’s PriorityQueue doesn’t reorder existing elements automatically.

Test Your Fixed Code #

Here’s a quick test case to confirm everything works:

public static void main(String[] args) {
    // Create nodes
    Node nodeA = new Node("A");
    Node nodeB = new Node("B");
    Node nodeC = new Node("C");
    Node nodeD = new Node("D");

    // Add edges with weights
    nodeA.adjacencies.add(new Edge(nodeB, 10));
    nodeA.adjacencies.add(new Edge(nodeC, 3));
    nodeB.adjacencies.add(new Edge(nodeC, 1));
    nodeB.adjacencies.add(new Edge(nodeD, 2));
    nodeC.adjacencies.add(new Edge(nodeB, 4));
    nodeC.adjacencies.add(new Edge(nodeD, 8));

    computePaths(nodeA);
    System.out.println("Shortest distance from A to D: " + nodeD.shortestDistance);
    // Should output 11 (A -> C -> B -> D)
}

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