java实现dijkstra算法

Dijkstra算法是用于解决单源最短路径问题的一种高效算法，特别是在有向无环图（DAG）或带权重的边的图中。在Java中实现Dijkstra算法，你可以使用优先队列（通常使用`java.util.PriorityQueue`）来存储尚未确定最短路径的节点，以及一个哈希映射或邻接表来存储图的结构。

以下是Java实现Dijkstra算法的一个基本步骤：

1. 初始化：创建一个HashMap或类似的数据结构，将起点的距离设为0，其他所有节点的距离设为无穷大，同时标记为未访问。

2. 创建优先队列：将起点放入队列，并设置其优先级为起点距离。

3. 主循环：从队列中取出当前距离最小的节点（通常是最小优先级的节点），然后更新其相邻节点的距离，如果通过当前节点到达更短，就更新这些节点的距离并将它们加入队列。

4. 遍历邻接节点：对于每个相邻节点，检查通过当前节点到达它的路径是否比之前记录的更短。如果是，更新并标记该节点为已访问。

5. 重复步骤3和4，直到队列为空或找到终点。如果队列为空且未访问到终点，说明找不到从起点到终点的路径。

import java.util.*;

class Node implements Comparable<Node> {
    int id;
    int distance;
    Node previous;

    public Node(int id) {
        this.id = id;
        this.distance = Integer.MAX_VALUE;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class Dijkstra {
    // 使用PriorityQueue存储节点
    private PriorityQueue<Node> queue = new PriorityQueue<>();
    // 图的邻接表或哈希映射
    private Map<Integer, List<Node>> graph;

    public List<Node> dijkstra(int start) {
        // ... (初始化、添加起点到队列等)
        while (!queue.isEmpty()) {
            Node current = queue.poll(); // 取出距离最小的节点
            // 更新未访问的邻居
            for (Node neighbor : graph.get(current.id)) {
                int distanceToNeighbor = current.distance + neighbor.distance;
                if (distanceToNeighbor < neighbor.distance) {
                    neighbor.distance = distanceToNeighbor;
                    neighbor.previous = current;
                    queue.offer(neighbor);
                }
            }
        }
        // 返回从起点到终点的路径，如果找到
        return buildPath(start);
    }

    private List<Node> buildPath(int end) {
        List<Node> path = new ArrayList<>();
        Node currentNode = endNode(end);
        while (currentNode != null) {
            path.add(currentNode);
            currentNode = currentNode.previous;
        }
        Collections.reverse(path);
        return path;
    }

    // ... (获取结束节点的方法，可能需要一个额外的哈希映射存储每个节点的结束标识)
}