# 847. Shortest Path Visiting All Nodes

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`

``````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);
}
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;
}
};
``````

``````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 同步地址: _

https://github.com/grandyang/leetcode/issues/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

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation