This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging
Topic describes
This is 847 on LeetCode. Shortest path to access all nodes, difficulty is difficult.
Tag: graph, Graph theory BFS, Dynamic programming, state compression
There exists an undirected connected graph consisting of n nodes numbered from 0 to N-1.
I give you an array graph to represent this graph. Graph [I] is a list of all the nodes that are directly connected to node I.
Returns the length of the shortest path that can access all nodes. You can start and stop at any node, revisit nodes multiple times, and reuse edges.
Example 1:
Input: graph = [[1, 2, 3], [0], [0], [0]] output: 4: a possible path for,0,2,0,3 [1]Copy the codeExample 2:
Input: graph = [[1], [0, 4-trichlorobenzene], [1 4], [2], [1, 2]] output: 4: a possible path for,1,4,2,3 [0]Copy the codeTip:
- n == graph.length
- 1 <= n <= 12
- 0 <= graph[i].length < n
- Graph [I] does not contain I
- If graph[a] contains B, then graph[b] also contains A
- The input graph is always connected
Fundamental analysis
For convenience, let the number of points be NNN and the number of edges be MMM.
This is an equally weighted undirected graph, and they want us to find the shortest path from “none of the points are accessed” to “all of the points are accessed.”
While the NNN is only 121212, it is easy to think of using “state compression” to represent the “access state of the current point” : using the low 121212 of the binary int of length 323232 to indicate whether it has been accessed.
We can get a sense of what state compression means by looking at a specific example:
For example, 000… 2 (0101) 000… 0101) _2 (000… 0101)2 indicates that nodes 000 and 222 have been accessed, but node 111 has not been accessed.
Then take a look at some basic operations that can be performed using state compression:
Suppose that the variable statestatestate holds the “current point access status”. When we want to check whether the point numbered XXX is accessed, we can use the bit operation a = (state >> x) & 1, To obtain the binary representation of bit XXX in Statestatestate. If a is 111, node XXX has been accessed; if a is 000, node XXX has not been accessed.
By the same token, when we need to mark Numbers for XXX node has been visit, then you can use an operation state | 1 < < (x) to implement the tag.
State compression + BFS
Since it is an equal weight graph, it is easy to think of BFS to find the shortest path from one state to another.
At the same time, we need to know which point we can move to next, so besides recording the current point access state statestatestate, we also need to record the last step at which point uuu, so we need to use the binary group to record (state,u)(state, u)(state,u). Also use distdistdist to record the steps used to reach (state,u)(state, u)(state,u).
Some details: Since the number of points is small, use either an adjacency list or an adjacency matrix to store the graph. In this case, since the graphgraphGraph array is already given, you can use it as a “adjacencies list” without any additional graph saving operations.
Code:
class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// Initialize all (state, u) distances to infinity
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) Arrays.fill(dist[i], INF);
// Since we can start from any starting point, we first queue the starting point state and set the starting distance to 0
Deque<int[]> d = new ArrayDeque<>(); // state, u
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
d.addLast(new int[] {1 << i, i});
}
// BFS process, if it can reach point I from point U, update the distance and join the queue
while(! d.isEmpty()) {int[] poll = d.pollFirst();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : graph[u]) {
if (dist[state | (1 << i)][i] == INF) {
dist[state | (1 << i)][i] = step + 1;
d.addLast(new int[]{state | (1<< i), i}); }}}return -1; // never}}Copy the code- Time complexity: The number of points (states) is
, the number of edges is
.BFSThe upper bound of complexity is the number of points plus the number of edges, and the overall complexity is
- Space complexity: O(n∗2n)O(n * 2^n)O(n∗2n)
Floyd + DP
In fact, in the above approach, we have used a similar idea to DP state definition analysis. Even our progenitor design (state,u)(state, u)(state,u) looks like two dimensions of state definition.
So why don’t we use it
Is the status of the point from “no point has been accessed” to “visited” is
“And the final step falls on the point
And then run through DP to do it?
Because if we start from the “normal DP transition idea”, there is no topological order (there is a ring) between the states, which causes us to calculate a
, it depends on a state that is not guaranteed to have been computed/updated, so we cannot use conventional DP methods to solve it.
F [state][u] F [state’][v] F [state’][v] F [state’][v] F [state’][v] F [state’][v]f[state][u] F [state][u]
In the conventional DP transfer mode, there is no topology order between states, so we need to change the way of thinking to transfer.
For a StatestatEstate, we can enumerate the last point III as the last step to statestatEstate, and then enumerate the next point JJJ, Act as the next move (provided, of course, that bit III of statestatestate is 111 and bit JJJ is 000).
The Floyd algorithm can be used to solve the shortest path of any two points, and the complexity is O(n3)O(n^3)O(n3).
Code:
class Solution {
int INF = 0x3f3f3f3f;
public int shortestPathLength(int[][] graph) {
int n = graph.length;
int mask = 1 << n;
// Find the shortest path between two points
int[][] dist = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { dist[i][j] = INF; }}for (int i = 0; i < n; i++) {
for (int j : graph[i]) dist[i][j] = 1;
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); }}}// the DP process, if it is possible to get from I to j, uses the shortest distance (step) from I to j
int[][] f = new int[mask][n];
// Set the minimum distance (step size) of all states to infinity
for (int i = 0; i < mask; i++) Arrays.fill(f[i], INF);
// Since you can start from any point, you can set the minimum distance (step) of these points to 0
for (int i = 0; i < n; i++) f[1 << i][i] = 0;
// Enumerate all states
for (int state = 0; state < mask; state++) {
// Enumerate the points in the state that have been accessed
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) = =0) continue;
// Enumerate the points in the state that have not been accessed
for (int j = 0; j < n; j++) {
if (((state >> j) & 1) = =1) continue;
f[state | (1 << j)][j] = Math.min(f[state | (1<< j)][j], f[state][i] + dist[i][j]); }}}int ans = INF;
for (int i = 0; i < n; i++) ans = Math.min(ans, f[mask - 1][i]);
returnans; }}Copy the code- Time complexity: Floyd complexity is O(n3)O(n^3)O(n3); There are n∗ 2NN * 2^ NN ∗2n states in DP that need to be transferred, each of which is O(n)O(n)O(n) O(n)O(n ^2 * 2^n)O(n2∗2n). The overall complexity of O (Max (n3, n2 ∗ 2 n)) O (\ Max (n ^ 3, n ^ 2 * 2 ^ n)) O (Max (n3, n2 ∗ 2 n))
- Space complexity: O(n∗2n)O(n * 2^n)O(n∗2n)
AStar
Obviously, the “theoretical minimum modification cost” from StatestatEstate to state’state ‘state ‘is the number of different bits in the binary representation of the two.
At the same time, it is possible to obtain this “theoretical minimum modification cost” if and only if there is an edge between the position of 111 in StatestatEstate and 000 in state’state ‘state ‘.
Therefore, it is appropriate to directly use the number of different bits in the binary representations of the current state statestatestate and the final target state 1 << n as heuristic estimates.
Code:
class Solution {
int INF = 0x3f3f3f3f;
int n;
int f(int state) {
int ans = 0;
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) = =0) ans++;
}
return ans;
}
public int shortestPathLength(int[][] g) {
n = g.length;
int mask = 1 << n;
int[][] dist = new int[mask][n];
for (int i = 0; i < mask; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]); // state, u, val
for (int i = 0; i < n; i++) {
dist[1 << i][i] = 0;
q.add(new int[] {1<< i, i, f(i << 1)});
}
while(! q.isEmpty()) {int[] poll = q.poll();
int state = poll[0], u = poll[1], step = dist[state][u];
if (state == mask - 1) return step;
for (int i : g[u]) {
int nState = state | (1 << i);
if (dist[nState][i] > step + 1) {
dist[nState][i] = step + 1;
q.add(new int[]{nState, i, step + 1+ f(nState)}); }}}return -1; // never}}Copy the codeThe last
This is article No.847 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.