Dijkstra算法（也叫单源最短路径算法）

Dijkstra算法（也叫单源最短路径算法）是一种贪心算法，用于解决图中单个源点到其他所有节点的最短路径问题。算法的时间复杂度为O(n²)。

算法流程：

1. 初始化。将所有节点的最短距离初始化为无穷大，将源点的最短距离初始化为0。

2. 找到距离源点最近的未标记节点，标记该节点。

3. 更新该节点的相邻节点的最短距离。

4. 重复第2和第3步，直到所有节点都被标记为止。

算法实现：

Dijkstra算法可以使用优先队列来实现。具体实现步骤如下：

1. 将源点加入优先队列，距离为0。

2. 取出队列中距离最小的节点，更新该节点的相邻节点的距离。如果更新后的距离比之前的距离更小，就把该节点加入队列。

3. 重复第2步，直到队列为空或者找到了目标节点。

Dijkstra算法的实现可以基于优先队列或邻接表，下面分别给出两种实现方式的Java代码示例。

基于优先队列的实现方式：

import java.util.*;

public class Dijkstra {

    private static final int INF = Integer.MAX_VALUE; // 代表两点之间没有边

    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n]; // 存储源点到各个节点的最短距离
        boolean[] visited = new boolean[n]; // 记录是否已经访问过

        Arrays.fill(dist, INF); // 将所有节点的距离初始化为无穷大
        dist[start] = 0; // 源点到自身的距离为0

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{start, 0});

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

            if (visited[node]) {
                continue;
            }

            visited[node] = true;

            for (int neighbor = 0; neighbor < n; neighbor++) {
                int neighborDistance = graph[node][neighbor];

                if (neighborDistance != 0 && !visited[neighbor]) {
                    int newDistance = dist[node] + neighborDistance;
                    if (newDistance < dist[neighbor]) {
                        dist[neighbor] = newDistance;
                        pq.offer(new int[]{neighbor, newDistance});
                    }
                }
            }
        }

        // 输出结果
        for (int i = 0; i < n; i++) {
            System.out.println("Distance from node " + start + " to node " + i + " is " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] graph = new int[][]{
            {0, 1, 4, 0}, 
            {1, 0, 2, 5}, 
            {4, 2, 0, 1}, 
            {0, 5, 1, 0}
            };
        dijkstra(graph, 0);
    }
}

基于邻接表的实现方式：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class DijkstraAlgorithm {

    private static final int INF = Integer.MAX_VALUE; // 定义无穷大

    /**
     * 通过邻接表构建图
     * @param edges 边集合
     * @param n 图中节点数
     * @return 返回邻接表
     */
    public static ArrayList<int[]>[] buildGraph(int[][] edges, int n) {
        ArrayList<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[] { edge[1], edge[2] });
        }
        return graph;
    }

    /**
     * Dijkstra算法求最短路径
     * @param graph 邻接表
     * @param start 起点
     * @return 返回起点到各个点的最短路径
     */
    public static int[] dijkstra(ArrayList<int[]>[] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, INF); // 初始距离均为无穷大
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[] { start, 0 });

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNode = curr[0], currDist = curr[1];
            if (currDist > dist[currNode]) continue;
            for (int[] neighbor : graph[currNode]) {
                int nextNode = neighbor[0], nextDist = currDist + neighbor[1];
                if (nextDist < dist[nextNode]) {
                    dist[nextNode] = nextDist;
                    pq.offer(new int[] { nextNode, nextDist });
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][] { 
            { 0, 1, 10 }, 
            { 0, 2, 3 }, 
            { 1, 2, 1 }, 
            { 1, 3, 2 }, 
            { 2, 1, 4 }, 
            { 2, 3, 8 }, 
            { 2, 4, 2 }, 
            { 3, 4, 7 }, 
            { 4, 3, 9 } };
        int n = 5;
        ArrayList<int[]>[] graph = buildGraph(edges, n);
        int[] dist = dijkstra(graph, 0);
        System.out.println(Arrays.toString(dist)); // [0, 7, 3, 9, 5]
    }
}