通过所有节点的最短路径

Colin

June 19, 2020

4219 views

No comments

239 words

编程记录技术杂烩

# 问题

[LeetCode #847][1]

在一个无向连通图中寻找一个最短路径，这个路径通过图中的所有节点。这个路径的起点、终点任意，可以重复访问节点。

# 分析

此题由于可以重复访问节点，因此并不同于旅行商（TSP）问题。

下面使用BFS解决问题。此题的关键在于BFS的“状态节点”是什么，如何不重复状态。

因为需要知道到某状态时是否访问了所有的节点，因此需要记录N个节点的访问状态。这里可以用bool数组，可以用bitset。而由于N<12，2^12在int范围内，实际上我们可以用一个int来记录N个点的访问情况（二进制意义）。由于之前没有用过bitset，故下面使用的是bitset。

如何才能不走没有意义的多余的路呢？显然，不重复访问节点是不行的，因为有的图必须这样才能访问到所有的点，如样例1。考虑“状态”包含的信息，有：现在处于的点、已经访问过的点、当前状态已经走过的长度。举一些例子可以发现，如果要求前二者组成的“状态”不重复，就能保证不遗漏最优解，并且去掉很多没有意义的走法。这里应该是用到了BFS时队列前面的状态走过的边数一定不大于后面的状态这一特点，并且本题每条边长度都是1。因此位于同一点，并且访问过了相同的点的状态，肯定是前面的要比后面的好。

最后是何时结束BFS的问题。上面已经说过，因为前面的状态一定比后面的好，因此第一个走完全部点的状态就是最好的状态。因此只要找到第一个完成的状态就可以返回答案了。

# 代码

```cpp
class Solution
{
    struct State
    {
        int now;
        bitset<12> visited;
        int length;

State(): now(0), length(0) {};
    };
public:
    int shortestPathLength(vector<vector<int>>& graph)
    {
        // BFS
        const int N = graph.size();
        string completed_str("");
        for (int i = 0; i < N; i++)
            completed_str += '1';
        const bitset<12> completed_state(completed_str);
        int ans = 0x7fffffff;
        bool visited_state[N][1 << N];
        memset(visited_state, 0, sizeof(visited_state));

queue<State> q;
        for (int i = 0; i < N; i++)
        {
            State tmp;
            tmp.now = i;
            tmp.visited[i] = 1;
            q.push(tmp);
            visited_state[i][tmp.visited.to_ulong()] = 1;
        }
        while (q.size())
        {
            State nowsta = q.front();
            q.pop();
            if (nowsta.visited == completed_state)
            {
                ans = nowsta.length;
                break;
            }
            for (int j = 0; j < graph[nowsta.now].size(); j++)
            {
                int& nxt = graph[nowsta.now][j];
                if (nowsta.length + 1 < ans)
                {
                    // move to j
                    State newsta;
                    newsta.now = nxt;
                    newsta.length = nowsta.length + 1;
                    newsta.visited = nowsta.visited;
                    newsta.visited[nxt] = 1;
                    if (visited_state[nxt][newsta.visited.to_ulong()])
                        continue;
                    q.push(newsta);
                    visited_state[nxt][newsta.visited.to_ulong()] = 1;
                }
            } // end of for
        }
        return ans;
    }
};
```

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

Last modification：June 24, 2020