使用java编写单源最短路径，迪杰斯特拉算法

迪杰斯特拉(Dijkstra's Algorithm)是一种用于寻找图中两点之间最短路径的经典算法，常用于解决单源点的问题。在Java中实现这个算法，你需要做以下步骤：

1. 定义数据结构：通常会使用邻接矩阵或邻接表存储图，并创建一个优先队列（如`PriorityQueue`），用于存储节点及其距离。

2. 初始化：将起始节点的距离设置为0，其他所有节点的距离设为无穷大，表示未探索过。然后将起始节点放入优先队列。

3. 主循环：从优先队列中取出当前距离最小的节点，更新其相邻节点的距离（如果通过该节点到达更近）。同时，检查新发现的节点是否已经存在于优先队列，若不在则添加进去。

4. 检查终止条件：当优先队列为空或者找到目标节点时，算法结束。

5. 结果记录：最终，起始节点到每个节点的最短路径可以由经过的路径构成。

以下是简单的Java代码示例：

import java.util.*;

public class Dijkstra {
    private int[][] graph; // 图的邻接矩阵
    private PriorityQueue<int[]> pq; // 优先队列

    public List<Node> dijkstra(int start) {
        pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        int[] distances = new int[nodes];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        pq.offer(new int[]{start, 0});

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

            if (distances[node] < current[1]) continue; // 已经是最短了，跳过

            for (int neighbor : graph[node]) {
                int altDistance = current[1] + graph[node][neighbor];
                if (altDistance < distances[neighbor]) {
                    distances[neighbor] = altDistance;
                    pq.offer(new int[]{neighbor, altDistance});
                }
            }
        }

        // 填充路径数组
        List<Node> path = new ArrayList<>();
        int currentNode = target;
        while (currentNode != start) {
            path.add(new Node(currentNode));
            currentNode = parent[currentNode];
        }
        Collections.reverse(path); // 从终点逆序回溯
        path.add(new Node(start)); // 添加起点
        return path;
    }

    // 辅助数据结构和变量省略...
}