【刷穿 LeetCode】求「连通图经过所有点的最短路径」的三种方式 ：「BFS」&「Floyd + 状压 DP」 &「AStar 算法」

输入：graph = [[1,2,3],[0],[0],[0]]
输出：4
解释：一种可能的路径为 [1,0,2,0,3]
复制代码

输入：graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一种可能的路径为 [0,1,4,2,3]
复制代码

class Solution {
    int INF = 0x3f3f3f3f;
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int mask = 1 << n;
        // 初始化所有的 (state, u) 距离为正无穷
        int[][] dist = new int[mask][n];
        for (int i = 0; i < mask; i++) Arrays.fill(dist[i], INF);
        // 因为可以从任意起点出发，先将起始的起点状态入队，并设起点距离为 0
        Deque<int[]> d = new ArrayDeque<>(); // state, u
        for (int i = 0; i < n; i++) {
            dist[1 << i][i] = 0;
            d.addLast(new int[]{1 << i, i});
        }
        // BFS 过程，如果从点 u 能够到达点 i，则更新距离并进行入队
        while (!d.isEmpty()) {
            int[] poll = d.pollFirst();
            int state = poll[0], u = poll[1], step = dist[state][u];
            if (state == mask - 1) return step;
            for (int i : graph[u]) {
                if (dist[state | (1 << i)][i] == INF) {
                    dist[state | (1 << i)][i] = step + 1;
                    d.addLast(new int[]{state | (1 << i), i});
                }
            }
        }
        return -1; // never
    }
}
复制代码

class Solution {
    int INF = 0x3f3f3f3f;
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int mask = 1 << n;
        // Floyd 求两点的最短路径
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = INF;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) dist[i][j] = 1;
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        // DP 过程，如果从 i 能够到 j 的话，使用 i 到 j 的最短距离（步长）来转移
        int[][] f = new int[mask][n];
        // 起始时，让所有状态的最短距离（步长）为正无穷
        for (int i = 0; i < mask; i++) Arrays.fill(f[i], INF);
        // 由于可以将任意点作为起点出发，可以将这些起点的最短距离（步长）设置为 0
        for (int i = 0; i < n; i++) f[1 << i][i] = 0;
        // 枚举所有的 state
        for (int state = 0; state < mask; state++) {
            // 枚举 state 中已经被访问过的点
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 0) continue;
                // 枚举 state 中尚未被访问过的点
                for (int j = 0; j < n; j++) {
                    if (((state >> j) & 1) == 1) continue;
                    f[state | (1 << j)][j] = Math.min(f[state | (1 << j)][j], f[state][i] + dist[i][j]);
                }
            }
        }
        int ans = INF;
        for (int i = 0; i < n; i++) ans = Math.min(ans, f[mask - 1][i]);
        return ans;
    }
}
复制代码

class Solution {
    int INF = 0x3f3f3f3f;
    int n;
    int f(int state) {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (((state >> i) & 1) == 0) ans++;
        }
        return ans;
    }
    public int shortestPathLength(int[][] g) {
        n = g.length;
        int mask = 1 << n;
        int[][] dist = new int[mask][n];
        for (int i = 0; i < mask; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = INF;
            }
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]); // state, u, val
        for (int i = 0; i < n; i++) {
            dist[1 << i][i] = 0;
            q.add(new int[]{1<< i, i, f(i << 1)});
        }
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int state = poll[0], u = poll[1], step = dist[state][u];
            if (state == mask - 1) return step;
            for (int i : g[u]) {
                int nState = state | (1 << i);
                if (dist[nState][i] > step + 1) {
                    dist[nState][i] = step + 1;
                    q.add(new int[]{nState, i, step + 1 + f(nState)});
                }
            }
        }
        return -1; // never
    }
}
复制代码