单源最短路径算法步骤及代码（必须有每行注释）java语言

单源最短路径算法通常使用 Dijkstra 算法或 Bellman-Ford 算法。

以下是使用 Dijkstra 算法实现的单源最短路径算法，Java 代码如下：

import java.util.*;

public class DijkstraAlgorithm {

    // 定义邻接表存储图
    static class Edge {
        int to;
        int weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    static List<List<Edge>> graph = new ArrayList<>();

    // 添加边
    static void addEdge(int from, int to, int weight) {
        graph.get(from).add(new Edge(to, weight));
    }

    // Dijkstra 算法实现
    static int[] dijkstra(int source) {
        int[] dist = new int[graph.size()];  // 存储源点到各点的最短距离
        Arrays.fill(dist, Integer.MAX_VALUE);  // 初始化为无穷大
        dist[source] = 0;  // 源点到自己的距离为0
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));  // 小根堆，存储结点编号和距离
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int u = cur[0], d = cur[1];
            if (dist[u] < d) continue;  // 若已经更新过了，直接跳过

            for (Edge e : graph.get(u)) {
                int v = e.to, w = e.weight;
                if (dist[v] > dist[u] + w) {  // 更新最短距离
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        // 初始化图，此处以无向图为例
        int n = 5;
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        addEdge(0, 1, 1);
        addEdge(0, 2, 4);
        addEdge(1, 2, 2);
        addEdge(1, 3, 7);
        addEdge(2, 3, 1);
        addEdge(2, 4, 5);
        addEdge(3, 4, 3);

        int[] dist = dijkstra(0);  // 计算源点0到其他点的最短距离
        System.out.println(Arrays.toString(dist));  // 输出结果
    }
}

注释已经在代码中给出。