单源最短路径java代码

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

import java.util.*;

public class Dijkstra {
    static final int MAXN = 100005;
    static final int INF = Integer.MAX_VALUE;
    static int n, m, s; // n: 节点数, m: 边数, s: 源点编号
    static int[] dist = new int[MAXN]; // dist[i] 表示源点到 i 的最短距离
    static boolean[] vis = new boolean[MAXN]; // vis[i] 表示 i 是否已经确定了最短距离
    static int[][] edges = new int[MAXN][MAXN]; // edges[i][j] 表示 i 到 j 的边权，如果不存在则赋值为 INF

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        s = scanner.nextInt();

        // 初始化
        Arrays.fill(dist, INF);
        dist[s] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                edges[i][j] = INF;
            }
        }

        // 读入边
        for (int i = 1; i <= m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            edges[u][v] = w;
        }

        // Dijkstra 算法
        for (int i = 1; i <= n; i++) {
            // 选出未确定最短距离的距离源点最近的点
            int x = 0;
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (x == 0 || dist[j] < dist[x])) {
                    x = j;
                }
            }
            vis[x] = true;

            // 更新与 x 相邻的点的最短距离
            for (int j = 1; j <= n; j++) {
                if (edges[x][j] != INF) {
                    dist[j] = Math.min(dist[j], dist[x] + edges[x][j]);
                }
            }
        }

        // 输出结果
        for (int i = 1; i <= n; i++) {
            System.out.print(dist[i] + " ");
        }
        System.out.println();
    }
}

注意，这里的实现使用了邻接矩阵来存储图。如果使用邻接表，则可以减少空间复杂度和时间复杂度。