基于Dijkstra算法的大规模加权图最短路径Java实现需求

Got it, let's break down how to solve this problem efficiently while hitting the performance requirements.

Key Considerations for Performance #

Given the constraints (up to 20,000 nodes and 50,000 edges), we need:

• An adjacency list instead of an adjacency matrix (matrix would take O(M²) space, which is way too big for M=20000)
• A min-heap (priority queue) to always pick the node with the current shortest distance—this keeps the time complexity around O(N log M), which is perfect for the 2-second limit
• A distance array to track the shortest known distance to each node, so we don't reprocess nodes unnecessarily

Full Code Implementation #

import java.util.*;

// Edge class to store destination node and edge weight
class Edge {
    int target;
    int weight;

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

public class DijkstraShortestPath {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Read first line: M (nodes), N (edges), A (start), O (end)
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int start = scanner.nextInt();
        int end = scanner.nextInt();

        // Handle edge case: start == end
        if (start == end) {
            System.out.println(0);
            scanner.close();
            return;
        }

        // Initialize adjacency list
        List<List<Edge>> adjacencyList = new ArrayList<>(M);
        for (int i = 0; i < M; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Read all edges
        for (int i = 0; i < N; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int weight = scanner.nextInt();
            // Add directed edge u -> v
            adjacencyList.get(u).add(new Edge(v, weight));
            // Uncomment below if the graph is undirected (edges are bidirectional)
            // adjacencyList.get(v).add(new Edge(u, weight));
        }
        scanner.close();

        // Distance array: initialize to infinity (we'll use Integer.MAX_VALUE as stand-in)
        int[] dist = new int[M];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Priority queue: stores pairs of (current distance, node), sorted by smallest distance first
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentDist = current[0];
            int node = current[1];

            // If we've already found a shorter path to this node, skip processing
            if (currentDist > dist[node]) {
                continue;
            }

            // If we reached the end node, we can break early (optional but saves time)
            if (node == end) {
                break;
            }

            // Iterate through all neighbors
            for (Edge edge : adjacencyList.get(node)) {
                int neighbor = edge.target;
                int newDist = currentDist + edge.weight;

                // If this path to neighbor is shorter than the known distance, update and add to queue
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.add(new int[]{newDist, neighbor});
                }
            }
        }

        // Output the result: if dist[end] is still infinity, no path exists
        if (dist[end] == Integer.MAX_VALUE) {
            System.out.println(-1); // Or any indicator for no path
        } else {
            System.out.println(dist[end]);
        }
    }
}

Notes on the Code #

• Edge Class: Simple container to hold the target node and weight of each edge.
• Adjacency List: Uses List<List<Edge>> to efficiently store only existing edges, saving memory.
• Priority Queue: We use an array of int[] where the first element is the distance and the second is the node, sorted by distance.
• Early Termination: Once we pop the end node from the priority queue, we can break early since Dijkstra's guarantees we've found the shortest path to it.
• Handling Large Weights: If your edge weights can sum to more than Integer.MAX_VALUE, switch to long for the distance array and queue elements to avoid overflow.

Quick Test Example #

For input:

5 6 0 4
0 1 2
0 2 5
1 2 1
1 3 3
2 4 2
3 4 1

The shortest path from 0 to 4 is 0->1->2->4 with total weight 5, so the code will output 5.

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