题目描述

给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。

graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

样例

输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]

输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一个可能的路径为 [0,1,4,2,3]

注意

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

算法1

(floyd + 状态压缩动态规划) $\Theta(n^3 + n^2 \cdot 2^n)$

1. 将原图通过 floyd 算法求出任意两点的最短路径。根据经典的求哈密尔顿路径的动态规划算法，状态 $f(S, i)$ 表示经过了 $S$ 集合中的点，且当前所在位置为 $i$ 的最短路径。
2. 转移时，枚举一个在 S 中的点，然后再枚举一个不在 S 中的点，通过 i 到 j 的路径长度，来进行转移。即 $f(S | (1 << j), j) = \min (f(S, i) + map(i, j))$。
3. 最终答案为枚举 $i$ 使得 $f((1 << n) - 1, i)$ 最小。

时间复杂度

• floyd 需要 $\Theta(n^3)$ 的时间，动态规划的状态数为 $\Theta (n \cdot 2^n)$ 个，每次需要 $\Theta(n)$ 的时间转移，故总时间复杂度为 $\Theta(n^3 + n^2 \cdot 2^n)$。

C++ 代码

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> map(n, vector<int>(n, n * n));
        vector<vector<int>> f(1 << n, vector<int>(n, n * n));

        for (int i = 0; i < n; i++)
            for (auto j : graph[i])
                map[i][j] = map[j][i] = 1;


        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

        for (int i = 0; i < n; i++)
            f[1 << i][i] = 0;

        for (int S = 0; S < (1 << n); S++)
            for (int i = 0; i < n; i++)
                if (S & 1 << i)
                    for (int j = 0; j < n; j++)
                        if (! (S & (1 << j)))
                            f[S | (1 << j)][j] = min(f[S | (1 << j)][j], f[S][i] + map[i][j]);

        int ans = n * n;
        for (int i = 0; i < n; i++)
            ans = min(ans, f[(1 << n) - 1][i]);
        return ans;
    }
};

算法2

(BFS) $O(n^2 \cdot 2^n)$

1. 状态 $f(S, i)$ 表示经过了 $S$ 集合中的点，且当前所在位置为 $i$ 的最短路径。
2. 如果 $i$ 和 $j$ 之间存在边，则 $(S, i)$ 到 $(S | (1 << j)), j)$ 建立边权为 1 的边，反之同理。
3. 由于边权都是 1，且转移的过程中可能会出现环，所以需要用 BFS 来代替普通的动态规划更新。

时间复杂度

• 图中总计 $O(n \cdot 2^n)$ 的点，$O(n^2 \cdot 2^n)$ 条边，按照 BFS 的时间复杂度，本算法的时间复杂度为 $O(n^2 \cdot 2^n)$。

C++ 代码

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<bool>> map(n, vector<bool>(n, false));
        vector<vector<int>> f(1 << n, vector<int>(n, n * n));

        for (int i = 0; i < n; i++)
            for (auto j : graph[i])
                map[i][j] = map[j][i] = true;

        queue<pair<int, int>> q;

        for (int i = 0; i < n; i++) {
            f[1 << i][i] = 0;
            q.push(make_pair(1 << i, i));
        }

        while (!q.empty()) {
            pair<int, int> sta = q.front();
            q.pop();
            int S = sta.first, i = sta.second;
            if (S == (1 << n) - 1)
                return f[S][i];
            for (int j = 0; j < n; j++)
                if (map[i][j] && f[S | (1 << j)][j] > f[S][i] + 1) {
                    f[S | (1 << j)][j] = f[S][i] + 1;
                    q.push(make_pair(S | (1 << j), j));
                }
        }
    }
};