使用java代码实现迪杰斯特拉算法

在Java中，我们可以使用`PriorityQueue`（优先队列）来实现Dijkstra算法，下面是一个基本的示例，假设我们有一个邻接矩阵`graph`来表示图，其中`graph[i][j]`代表从节点i到节点j的边的权重：

import java.util.*;

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE / 2; // 设置一个较大的初始距离值

    public List<int[]> dijkstra(int[][] graph, int start) {
        int n = graph.length;
        Node[] nodes = new Node[n];
        Arrays.fill(nodes, new Node(INF, -1)); // 初始化所有节点距离为无穷大，父节点为-1
        nodes[start].distance = 0; // 起点距离为0

        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.distance - b.distance); // 按距离排序
        pq.offer(nodes[start]); // 入队起始节点

        while (!pq.isEmpty()) {
            Node current = pq.poll(); // 出队距离最近的节点
            if (current.distance == INF) break; // 找到终点或无路可达

            for (int i = 0; i < n; i++) {
                if (graph[current.id][i] != 0 && current.distance + graph[current.id][i] < nodes[i].distance) { // 更新邻居节点距离
                    nodes[i].distance = current.distance + graph[current.id][i];
                    nodes[i].parent = current.id; // 更新父节点
                    pq.offer(nodes[i]);
                }
            }
        }

        return reconstructPath(nodes, start, end); // 构造最短路径
    }

    // 辅助函数：回溯路径
    private List<int[]> reconstructPath(Node[] nodes, int start, int end) {
        List<int[]> path = new ArrayList<>();
        int curr = end;
        while (curr != -1) {
            path.add(new int[]{curr, nodes[curr].parent});
            curr = nodes[curr].parent;
        }
        Collections.reverse(path);
        return path;
    }

    private class Node {
        int id;
        int distance; // 到起点的距离
        int parent; // 父节点id
        public Node(int d, int p) {
            this.distance = d;
            this.parent = p;
        }
    }
}

在这个例子中，`dijkstra`方法接受一个图和起点作为输入，返回从起点到终点的最短路径列表。如果到达终点，`reconstructPath`会帮助我们反向追踪路径。请注意，在实际应用中，您需要根据需求调整这个实现，比如处理负权边等情况。