贪心算法单源最短路径:Djikstra算法Java实现

贪心算法是一种启发式搜索策略，在解决优化问题时通常会选择当前状态下看起来最优的选择，希望能找到全局最优解。而在单源最短路径问题中，Dijkstra算法是一个经典的求解方法，它适用于带权重的有向图或无向图，目标是从起点到所有其他节点的最短路径。

以下是Dijkstra算法的一个简单的Java实现：

import java.util.*;

class Dijkstra {
    private int V; // 图的顶点数
    private int[] dist; // 存储每个顶点的最短距离
    private PriorityQueue<int[]> pq; // 优先队列

    public Dijkstra(int v) {
        V = v;
        dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0});
    }

    public void dijkstra(int src) {
        dist[src] = 0;

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[1];

            if (dist[u] < curr[0]) continue; // 已经更新过更短的距离，跳过

            for (int v : adj[u]) { // 遍历邻接表
                int alt = dist[u] + weight(u, v); // 新的边长
                if (alt < dist[v]) {
                    dist[v] = alt;
                    pq.offer(new int[]{alt, v}); // 更新优先队列
                }
            }
        }
    }

    // 边的权值计算函数
    private int weight(int u, int v) {
        // 根据实际需求实现，这里假设是常量
        return 1;
    }
}

// 使用示例
public static void main(String[] args) {
    Dijkstra dijkstra = new Dijkstra(5);
    dijkstra.dijkstra(0);
    // 输出dist数组，即从源节点0到其他各节点的最短距离
}