Dijkstra 算法

Dijkstra 算法使用邻接矩阵 graph 来存图，graph[i][j] 表示节点 i 到 j 的边的权重。如果两个节点没有边，则权重为 ∞。

找节点 start 和节点 end 之间的最短路径时，定义一个 dis 数组，dis[i] 表示从 start 到节点 i 的最短路的长度。

从 start 出发，更新邻居的最短路。
寻找尚未 visited 的节点中 dis 的最小值 dis[x]，则 dis[x] 是节点 start 和节点 end 之间的最短路径。
更新最短路长度。

class Graph {
    private static final int INF = Integer.MAX_VALUE / 2; // 防止更新最短路时加法溢出

    private int[][] g;

    public Graph(int n, int[][] edges) {
        g = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
        for (int i = 0; i < n; ++i)
            Arrays.fill(g[i], INF);
        for (var e : edges)
            g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边）
    }

    public void addEdge(int[] e) {
        g[e[0]][e[1]] = e[2]; // 添加一条边（输入保证这条边之前不存在）
    }

    // 朴素 Dijkstra 算法
    public int shortestPath(int start, int end) {
        int n = g.length;
        int[] dis = new int[n]; // 从 start 出发，到各个点的最短路，如果不存在则为无穷大
        Arrays.fill(dis, INF);
        dis[start] = 0;
        int[] vis = new boolean[n];
        // 注意，vis[start] 一开始可不能马上变成 true!
        for (;;) {
            // 找到当前最短路，去更新它的邻居的最短路
            // 根据数学归纳法，dis[x] 一定是最短路长度
            int x = -1;
            for (int i = 0; i < n; ++i)
                if (!vis[i] && (x < 0 || dis[i] < dis[x]))
                    x = i;
            if (x < 0 || dis[x] == INF) // 所有从 start 能到达的点都被更新了
                return -1;
            if (x == end) // 找到终点，提前退出
                return dis[x];
            vis[x] = true; // 标记，在后续的循环中无需反复更新 x 到其余点的最短路长度
            for (int y = 0; y < n; ++y)
                dis[y] = Math.min(dis[y], dis[x] + g[x][y]); // 更新最短路长度
        }
    }
}

练习题

Floyd 算法

Floyd 本质是动态规划。

定义 d[k][i][j] 表示从 i 到 j 的最短路长度，并且从 i 到 j 的路径上的中间节点（不含 i 和 j）的编号至多为 k。

分类讨论：

如果 i 到 j 的路径上的节点编号没有 k，那么按照定义 d[k][i][j]=d[k−1][i][j]。
如果 i 到 j 的路径上的节点编号有 k，那么可以视作先从 i 到 k，再从 k 到 j。由于 i 到 k 和 k 到 j 的中间节点都没有 k，所以有 d[k][i][j]=d[k−1][i][k]+d[k−1][k][j]。
取最小值，得

d[k][i][j]=min(d[k−1][i][j],d[k−1][i][k]+d[k−1][k][j])

初始值 d[0][i][j]为原图中 i 到 j 的边长，如果不存在则为 ∞。最终 i 到 j 的最短路长度为 d[k−1][i][j]。

代码实现时，第一个维度可以优化掉，即

d[i][j]=min(d[[i][j],d[i][k]+d[k][j])

class Graph {
    private static final int INF = Integer.MAX_VALUE / 3; // 防止更新最短路时加法溢出

    private int[][] d;

    public Graph(int n, int[][] edges) {
        d = new int[n][n]; // 邻接矩阵（初始化为无穷大，表示 i 到 j 没有边）
        for (int i = 0; i < n; ++i) {
            Arrays.fill(d[i], INF);
            d[i][i] = 0;
        }
        for (var e : edges)
            d[e[0]][e[1]] = e[2]; // 添加一条边（输入保证没有重边和自环）
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
    }

    public void addEdge(int[] e) {
        int x = e[0], y = e[1], w = e[2], n = d.length;
        if (w >= d[x][y]) // 无需更新
            return;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                d[i][j] = Math.min(d[i][j], d[i][x] + w + d[y][j]);
    }

    public int shortestPath(int start, int end) {
        int ans = d[start][end];
        return ans < INF / 3 ? ans : -1;
    }
}