leetcode 847 访问所有节点的最短路径 题解

发表于 | 更新于

题目

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:

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

Example 2:

1
2
3
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

解法一

这周刚好学到了BFS、Dijkstra、Bellman–Ford等处理图论问题的算法，这里就能够用上了。这一题是要在无向图中找到经过了每一个节点的最短路径，可以很快想到可以用BFS算法，但是再一想，BFS算法可以用来找两点间最短路径，而这里并没有给出起点和终点，只是单纯的找到一条经过每个节点的最短路径，怎么办呢？

以往使用BFS算法时，是将节点不断加入、弹出队列，在这里我们可以换种思路，比如把从各个节点开始的路径加入、更新、弹出队列，并记录此时路径对应的长度，直到队列为空时，此时经过了所有节点的路径的长度应该被更新了许多次，达到了最小。

首先需要构建一个struct类型，代表此时的路径状态：

1
2
3
4
5
6
7
struct state{
    int visited, tovisit;	//已经过的节点，要访问的节点
    state(int v, int t){
        visited = v;
        tovisit = t;
    }
};

用bits来记录经过的节点：从第n号节点开始即为1 << n = 1...00（n个0），访问完所有节点的路径状态应该是011..1，哪一位为1即代表经过了哪一位，访问节点的邻居后的节点状态这样表示：visited | (1 << neighbour)。

接下来是实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int shortestPathLength(vector<vector<int>>& graph) {
    int n = graph.size();
    queue<state> mqueue;
    vector<vector<int>> dist(1 << n, vector<int>(n, n * n));
    for(int i = 0; i < n; i++){
        mqueue.push(state(1 << i, i));	//queue中一开始设置各个节点开始的初始路径
        dist[1 << i][i] = 0;
    }
    while(!mqueue.empty()){
        state node = mqueue.front();
        mqueue.pop();
        int dis = dist[node.visited][node.tovisit];
        if(node.visited == (1 << n) - 1) return dis;
        for(int neighbour : graph[node.tovisit]){	//通过graph访问节点邻居
            int visited2 = node.visited | (1 << neighbour);
            if(dis + 1 < dist[visited2][neighbour]){	//路径更短则更新
                dist[visited2][neighbour] = dis + 1;
                mqueue.push(state(visited2, neighbour));	//更新后的路径状态再加入queue
            }
        }
    }
}

比较难想到的地方就是对路径状态进行BFS。

解法二

通过官方solution发现了第二种使用了Dynamic Programming的解法，大体上其实和BFS差不多，都是对路径状态进行操作。

解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int shortestPathLength(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dist(1 << n, vector<int>(n, n * n));
    for(int i = 0; i < n; i++){
        dist[1 << i][i] = 0;
    }
    for(int visited = 0; visited < 1 << n; ++visited){
        bool repeat = true;
        while(repeat){
            repeat = false;
            for(int tovisit = 0; tovisit < n; ++tovisit){
                int dis = dist[visited][tovisit];
                for(int neighbour : graph[tovisit]){
                    int visited2 = visited | (1 << neighbour);
                    if(dis + 1 < dist[visited2][neighbour]){
                        dist[visited2][neighbour] = dis + 1;
                        if(visited2 == visited) repeat = true;
                    }
                }
            }
        }
    }
    int ans = n * n;
    for(int i : dist[(1 << n) - 1]){
        ans = min(i, ans);
    }
    return ans;
}

可以看到，这种解法是通过多重循环，对dist中每一种路径状态进行更新，最后取都是经过每个节点的路径中最短的一条。