Skip to content

847. Shortest Path Visiting All Nodes

847. Shortest Path Visiting All Nodes

题目: https://leetcode.com/problems/shortest-path-visiting-all-nodes/

难度: Hard

题意：

  1. 给定一个图，问走遍所有的点的最短距离是多少

思路：

  • 这个题首先考虑一下dfs的做法。假设我们已经到达了m个点，下个点，我们需要枚举所有下个点没有被访问的点，进行访问遍历，直到所有的点都被访问到
  • 我们注意到，枚举的过程中，需要枚举所有下个点没有被访问的点，而这个跟先前访问的顺序无关，也就是状态是一个访问集合，和当前到达的点共同组合而成的
  • 我们注意到，枚举的过程中，状态是需要重复访问，因此我们利用记忆化搜索，保存中间结果，进行动态规划
  • 这里需要注意的，我们可以预先把图形中两两最短距离先求出来缓存起来，这一部分只需要o(n^3)的复杂度
  • 子问题是：f(set, last)，set是访问集合，last是当前到达的点，函数值是达到当前状态最短距离
  • 这里有个代码的实现方式，集合如何用实现？当然如果想实现一个具备集合特性的数据结构也是可以的，最简单的方式就是用bitset，也就是把集合的信息压缩在一个二进制串中，这个题的数据范围是n<=12，因此一个int就可以表达状态，状态总量是2^n*n，因此这个动态规划的时间复杂度是o(2^n*n^2)

代码：

class Solution {
     private int solve(int set, int last, int[][] dist, int[][] cache) {
        if (cache[set][last] != -1) {
            return cache[set][last];
        }

        if (set == (1 << dist.length) - 1) {
            return cache[set][last] = 0;
        }

        int ret = 0x3fffffff;
        for (int i = 0;i < dist.length;i++) {
            if ((set & (1 << i)) == 0) {
                ret = Math.min(ret, dist[last][i] + solve(set + (1 << i), i, dist, cache));
            }
        }
        return cache[set][last] = ret;
    }

    private int[][] calDist(int[][] graph) {
        int[][] dist = new int[graph.length][graph.length];
        for (int i = 0;i < graph.length;i++) {
            for (int j = 0;j < graph.length;j++) {
                dist[i][j] = 0x3fffffff;
            }
        }
        for (int i = 0;i < graph.length;i++) {
            dist[i][i] = 0;
            for (int j = 0;j < graph[i].length;j++) {
                dist[i][graph[i][j]] = 1;
            }
        }
        for (int k = 0;k < graph.length;k++) {
            for (int i = 0;i < graph.length;i++) {
                for (int j = 0;j < graph.length;j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        return dist;
    }

    public int shortestPathLength(int[][] graph) {
        int[][] cache = new int[1 << graph.length][graph.length];
        for (int i = 0;i < (1 << graph.length);i++) {
            for (int j = 0;j < graph.length;j++) {
                cache[i][j] = -1;
            }
        }
        int[][] dist = calDist(graph);
        int ret = 0x3fffffff;
        for (int i = 0;i < graph.length;i++) {
            ret = Math.min(ret, solve((1 << i), i, dist, cache));
        }
        return ret;
    }
}
回到顶部