[LeetCode] 847. Shortest Path Visiting All Nodes

[grandyang]

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Note:

1. 1 <= graph.length <= 12
2. 0 <= graph[i].length < graph.length

这道题说是给了一个无向图，里面有N个结点，让我们找到一条可以经过所有结点的路径，该路径的起点和终点任意选，只要能经过所有结点即可，这里的每个结点和边都可以重复经过，问这样一条路径的最短长度是多少，注意这里的长度不是路径结点的个数，而是结点中的边的个数。先来想一下，假如这些结点是一字排开的，则最短经过所有结点的路径就类似于遍历链表一样的，但假如这些结点是围绕着一个中心结点的话，比如本题中的例子1，则中心结点会被经过多次，感觉不太好整啊。博主之前说过求极值的问题有两大神器，动态规划 Dynamic Programming 和广度优先搜索 Breadth First Search，这里碰巧两种方法都能解。先来看看 BFS 的解法吧，这种解法最经典的应用是在迷宫问题中，找到起点和终点之间的最短距离，假如把每个位置都看作一个状态的话，BFS 可以推广到更一般的情况。在迷宫中每一步可能会有上下左右四个方向可以选，每走一步其实可以看作是一个状态转移到另一个状态，当到达终点状态时，就可以得到最少步数了。这里也是类似，首先要定义起始状态和终止状态，本题关心的是要经过所有的结点，终止状态就是经过所有结点，起始状态就是只经过了起始结点，那该如何编码这些状态呢？最直接的方法就是把经过的结点放到数组或者 HashSet 中，但是这样的话每次检验是否到达终止状态的时候，都要检测数组或者 HashSet 中是否包含了所有的结点，这会很费时，因为在 BFS 的每一层遍历中都会检测是否到达终止状态。还有就是每个状态是由当前遍历的结点跟当前结点标号组成的，假如把遍历过的结点放到数组或集合中，再跟当前结点标号一起组成 pair 对儿放入队列 queue 中，将会占用大量的空间。

基于以上分析，貌似必须想一种更好的方法来编码遍历过的结点，这里用到了位操作 Bit Manipulation 的技巧，对没使用过的童鞋来说会比较 tricky。对于任意结点i，假如遍历过了，则将其对应位上变为1，即 ‘或’ 上 1<<i，这样每个结点都可以被分别编码进对应位，则遍历过n个结点的十进制数就是 2^n-1 了，只要某个状态的十进制数等于 2^n-1，则表示到达了终止状态。另外，由于最短路径的起点不定，那么这里的 BFS 的起点就应该是所有的结点，将每个结点都当作起始结点，并将结点编号编码到十进制数中，和当前位置一起组成 pair 对儿放进队列中。将n个起点都放入队列之后，就可以开始遍历了，它们都属于同一层，这里进行的是 BFS 的层序遍历的形式。对于每个取出的元素，首先判断取出的状态的 pair 对儿的第一个编码十进制数是否等于最终结果值 target，是的话直接返回结果 res。然后再根据第二个位置值去 graph 数组中查找所有与其相邻的结点，对于每个相邻的结点 next，由于在之前的基础上又加上了结点 next，这也要编码进去，所以要 ‘或’ 上 1<<next，然后在 visted 集合中查找该新状态是否存在，不存在的话加入 visited 集合，并把编码成的十进制数 path 和当前结点编号 next 组成新的 pair 对儿加入队列进行下次遍历。每层遍历结束后记得结果 res 要自增1，while 循环退出后返回 -1，其实根本不会返回 -1，因为题目中是无向连通图，一定会有经过所有结点的路径存在，这里只是怕不写返回值会报错而已，参见代码如下：

解法一：

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size(), target = 0, res = 0;
        unordered_set<string> visited;
        queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i) {
            int mask = (1 << i);
            target |= mask;
            visited.insert(to_string(mask) + "-" + to_string(i));
            q.push({mask, i});
        }
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                auto cur = q.front(); q.pop();
                if (cur.first == target) return res;
                for (int next : graph[cur.second]) {
                    int path = cur.first | (1 << next);
                    string str = to_string(path) + "-" + to_string(next);
                    if (visited.count(str)) continue;
                    visited.insert(str);
                    q.push({path, next});
                }
            }
            ++res;
        }
        return -1;
    }
};

再来看一种 DP 的解法，这种解法的核心思想跟上面的 BFS 方法很类似，我们用一个二维的 dp 数组，其中 dp[i][j] 表示的某个状态时经过的结点编码成的十进制数i，且当前位置为结点j时的路径长度。这样的话只要当i到达 2^n-1 的时候，此时所有的 dp[2^n-1][j] 中的最小值即为所求，这种定义状态的方式可以说和上面的解法完全一样。就像上面解法中将n个结点都当作起始点，并将其状态存入队列中的操作一样，这里要将所有的 dp[1<<i][i] 初始化为0，然后遍历所有可能的十进制编码值 cur，从0到 2^n-1，新建一个 boolean 型变量 repeat，进行 repeat 为 true 的循环。在循环中，先将 repeat 赋值为 false，然后遍历所有结点，对于遍历到的结点i，取出其编码值为 cur 的 dp 值 dist，然后遍历与其相连的所有结点，对于每个遍历到的结点 next，还是先用 cur ‘或’ 上 1<<next 得到新的编码值，然后进行松弛操作 Relaxation，即若 dp[path][next] 值大于 dist+1，则用 dist+1 来更新 dp[path][next]。同时判断若 path 和 cur 相等，将 repeat 赋值为 true，从而需要再次进行循环。因为若 path 等于 cur，说明该相邻结点 next 在之前已经被编码进 cur 了，但依然能进行松弛操作的话，就需要再次遍历一遍所有结点，以保证在当前编码 cur 的情况下，将所有的松弛操作都进行完。最后用 dp 数组的最后一行来更新结果 res，其中的最小值即为所求，参见代码如下：

解法二：

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size(), res = n * n;
        vector<vector<int>> dp(1 << n, vector<int>(n, n * n));
        for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;
        for (int cur = 0; cur < (1 << n); ++cur) {
            bool repeat = true;
            while (repeat) {
                repeat = false;
                for (int i = 0; i < n; ++i) {
                    int dist = dp[cur][i];
                    for (int next : graph[i]) {
                        int path = cur | (1 << next);
                        if (dist + 1 < dp[path][next]) {
                            dp[path][next] = dist + 1;
                            if (path == cur) repeat = true;
                        }
                    }
                }
            }
        }
        for (int num : dp.back()) {
            res = min(res, num);
        }
        return res;
    }
};

Github 同步地址:

#847

类似题目：

Shortest Path to Get All Keys

参考资料：

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

https://leetcode.com/problems/shortest-path-visiting-all-nodes/discuss/135712/Java-BFS

https://leetcode.com/problems/shortest-path-visiting-all-nodes/discuss/152679/Short-Java-Solution-BFS-with-a-Set

LeetCode All in One 题目讲解汇总(持续更新中...)

[lld2006]

我觉得是不是可以不用string， 因为最多只有12个node， 4bit位就可以代表了， 12位代表访问的flag，用个vector就可以了， 不需要unordered_set

[grandyang]

我觉得是不是可以不用string， 因为最多只有12个node， 4bit位就可以代表了， 12位代表访问的flag，用个vector就可以了， 不需要unordered_set

求贴代码～

[lld2006]

class Solution {
public:
  using IntPair = pair < int, int >;
    int shortestPathLength(vector>& graph) {
      if(graph.size() <= 1) return 0;
      queue q;       
      vector visited(1<<(graph.size()+4), false);  //index is current node  + flag for all nodes visit status
      for(int i = 0; i < graph.size(); ++i){
        q.emplace(i, 1<< i);
        visited[(1 << i) | (i  << graph.size())] = true;
      }
      int distance = 0;
      while(!q.empty()){
        int qsize = q.size();
        ++distance;
        for(int i = 0; i < qsize; ++i){
          auto p = q.front(); 
          int node = p.first;
          int flag = p.second;
          q.pop();
          for(int neighbor : graph[node]){
            int new_flag = (flag | (1 << neighbor));
            if(new_flag == (1 << graph.size())-1) return distance; //no need to continue once find one minimum
            if(visited[new_flag | (neighbor << graph.size())]) continue;
            visited[new_flag | (neighbor << graph.size())] = true;
            q.emplace(neighbor, new_flag);
          }
        }
      }
      return distance;
    }
};