This is the sixth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Leetcode -847- Shortest path to access all nodes

[Blog link]

The way to study 🐔

The nuggets home page

[Topic description]

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
Explanation:One possible path is [1,0,2,0,3]

Example 2:

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

 

Tip:

• n == graph.length
• 1 <= n <= 12
• 0 <= graph[i].length < n
• graph[i]Does not containi
• ifgraph[a]containsb, thengraph[b]Also containsa
• The input graph is always connected

Idea 1: Undirected graph +BFS+ binary

• Given an array of inputs that are already undirected, how do you build an undirected graph
• It is easy to figure out the BFS search method if you can think of the triple set up by the official problem solving
• Too bad
• Define an object structure “u” “mask” “dist”
  • U indicates the index of the current node
  • Mask indicates the sequence of nodes that have been accessed (the index position of the nodes that have been accessed is 1, and the rest are 0)
  • Dist Length of the path passed by the current node
• BFS traverses this object structure
• Until all bits of mask are 1
• Dist as the answer
• You also need to use the hash or visited array to record the traversal nodes to prevent invalid repeated traversal

class Node {
    int idx;
    int mask;
    int dist;

    public Node(int idx, int mask, int dist) {
        this.idx = idx;
        this.mask = mask;
        this.dist = dist; }}public int shortestPathLength(int[][] graph) {
    Deque<Node> dq = new ArrayDeque<>();
    boolean[][] visited = new boolean[graph.length][1 << graph.length];
    for (int i = 0; i < graph.length; i++) {
        dq.add(new Node(i, 1 << i, 0));
        visited[i][1 << i] = true;
    }
    int ans = 0;
    while(! dq.isEmpty()) { Node temp = dq.pollFirst();if (temp.mask == (1 << graph.length) - 1) {
            ans = temp.dist;
            break;
        }
        for (int num : graph[temp.idx]) {
            int newMask = temp.mask | (1 << num);
            if(! visited[num][newMask]) { dq.add(new Node(num, newMask, temp.dist + 1));
                visited[num][newMask] = true; }}}return ans;
}
Copy the code

Time complexity
$O(n^{2}*2^{n})$

Tips: I don’t know why, but hash makes TLE

---

Idea 2: State compression + tuple

• Trilobite’s tuples save on defining structs
• Dist [u][state] indicates the related access status of u node to other nodes

public int shortestPathLength(int[][] graph) {
    int INF = 0x3f3f3f3f, mask = 1 << graph.length, n = graph.length;
    int[][] dist = new int[n][mask];
    // Initialize all arrays
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
    }
    Deque<int[]> deque = new ArrayDeque<>();
    // Each node can start
    for (int i = 0; i < n; i++) {
        dist[i][1 << i] = 0;
        deque.addLast(new int[]{i, 1 << i});
    }
    while(! deque.isEmpty()) {int[] temp = deque.poll();
        int u = temp[0], state = temp[1], step = dist[u][state];
        if (state == mask - 1) {
            return step;
        }
        for (int num : graph[u]
        ) {
            if (dist[num][state | (1 << num)] == INF) {
                dist[num][state | (1 << num)] = step + 1;
                deque.add(new int[]{ num,state | (1<< num)}); }}}return -1;
}
Copy the code

Time complexity
$O(n^{2}*2^{n})$

---

Idea 3: State compression + DP + tuple + Floyd to find the shortest path

• Mitsuha’s mind is really good
• This tuple looks a lot like DP
• It’s just different from regular DP
• Conventional DP does not double count (which corresponds to the concept of ring)
• In this case, there is a ring (topological sort), that is, the calculation will be repeated
• So you can’t use normal DP to solve for it
• The first step initializes the distance array dist[I][j] to represent the steps from I to j with each value INF (maximum)
• Step 2 scans each node to the first reachable node dist 1
• Part three Floyd finds the shortest path
• K nodes are related nodes. Determine whether each node is shortest from I -> k ->j or directly from I ->j
• Set up the dp array f[I][state] to represent the state using the shortest possible route from I to j
  • I for node
  • State indicates the arrival state
• This problem is completely the three-lobe idea, but I don’t understand why dp starts with state and goes through the outermost layer, right
• After reading lc’s reply, I suddenly realized that each node does not start with a separate state, so it is not accurate to make a transition according to the node, but to make a transition according to the state. One node corresponds to multiple states

public int shortestPathLength(int[][] graph) {
    int n = graph.length, mask = 1 << n, INF = 0x3f3f3f3f;
    int[][] dist = new int[n][n];
    // Find the shortest path
    // Initialize the array
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) { dist[i][j] = INF; }}// Moving from all nodes to the moveable j node is a step from I to j
    for (int i = 0; i < n; i++) {
        for (int j : graph[i]) dist[i][j] = 1;
    }
    // Find the shortest path
    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]); }}}// Start dynamic programming
    int[][] f = new int[n][mask];
    // Initialize the equation of state
    for (int i = 0; i < n; i++) {
        Arrays.fill(f[i], INF);
    }
    // Initialize the initial node state. The current state is 0 bits
    for (int i = 0; i < n; i++) {
        f[i][1 << i] = 0;
    }
    for (int state = 0; state < mask; state++) {
        for (int i = 0; i < n; i++) {
            // The current state is the initial node state. You do not need to scan the initial node again
            if ((state & (1 << i)) == 0) continue;
            for (int k = 0; k < n; k++) {
                // The next node corresponding to the current state is also scanned
                if ((state & (1 << k)) == 1) continue;
                // Enumerates the current unscanned state
                f[k][state | (1 << k)] = Math.min(f[k][state | (1<< k)], f[i][state] + dist[i][k]); }}}int ans = INF;
    for (int i = 0; i < n; i++) ans = Math.min(ans, f[i][mask - 1]);
    return ans;

}
Copy the code

Max (n^{3}, n^{2}2^{n})