dijkstra算法java实现

Dijkstra算法是一种用于寻找图中两点之间最短路径的贪心算法，通常用于解决单源最短路径问题。在Java中实现Dijkstra算法，你可以按照以下步骤进行：

1. 初始化：创建一个优先队列（通常使用`PriorityQueue`或自定义最小堆），存储顶点和它们的距离（初始时距离为无穷大，源节点距离为0）。

2. 创建邻接表或邻接矩阵表示图。

3. 主循环：
a. 从队列中取出当前最短距离的节点。
b. 更新与其相邻节点的距离，如果通过当前节点到达更短，更新距离，并标记该节点已访问。
c. 将未访问的邻居节点加入队列。

4. 当队列为空或找到目标节点时，算法结束。此时队列中的最后一个元素即为目标节点，且所有节点的距离值即是最短路径。

以下是简单的Java代码实现：

import java.util.*;

public class Dijkstra {
    private final int V; // 图的顶点数
    private List<List<Edge>> adj; // 邻接列表
    private int[] dist; // 存储每个节点到源的距离

    // 边类，包含起点、终点和权重
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public Dijkstra(int v, List<List<Edge>> adj) {
        this.V = v;
        this.adj = adj;
        dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist = 0;
    }

    // Dijkstra算法核心部分
    public void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, 0, 0)); // 元素为 (距离, 节点, 来源)

        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            int u = curr.dest; // 当前节点
            if (dist[u] < curr.weight) continue; // 已经找到更短路径，跳过

            for (Edge e : adj.get(u)) {
                int v = e.dest, alt = dist[u] + e.weight;
                if (alt < dist[v]) {
                    dist[v] = alt;
                    pq.removeIf(edge -> edge.src == v); // 如果找到更短路径，移除旧路径
                    pq.offer(new Edge(v, alt, u)); // 添加新路径
                }
            }
        }
    }

    // 返回源节点到所有其他节点的最短距离
    public int[] printDistances() {
        return dist;
    }

    // 示例用法
    public static void main(String[] args) {
        List<List<Edge>> adj = new ArrayList<>(); // 图的邻接列表构建
        // 填充邻接列表...
        Dijkstra dijkstraAlg = new Dijkstra(V, adj);
        dijkstraAlg.dijkstra();
        int[] shortestDist = dijkstraAlg.printDistances();
    }
}