首页 > itarticle > [leetcode] problem 847 – shortest path visiting all nodes

[leetcode] problem 847 – shortest path visiting all nodes

admin 11月 13, 2020 0

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

No.1

Input: [[1,2,3],[0],[0],[0]]

Output: 4

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

No.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

Code

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
public class {
    private int currentNode;
    private int visitedNode;

    public (int currentNode, int visitedNode) {
        this.currentNode = currentNode;
        this.visitedNode = visitedNode;
    }
}

public int shortestPathLength(int[][] graph) {
    int result = 0;
    int n = graph.length;
    int target = (1 << n) - 1;
    boolean[][] visit = new boolean[n][1 << n];
    Queue<State> queue = new LinkedList<>();

    for (int i = 0; i < n; i++)
        queue.offer(new State(i, 1 << i));

    while (!queue.isEmpty()) {
        int size = queue.size();

        for (int i = 0; i < size; i++) {
            State state = queue.poll();

            if (state.visitedNode == target)
                return result;

            for (int nextNode : graph[state.currentNode]) {
                int nextVisitedNode = state.visitedNode | 1 << nextNode;

                if (visit[nextNode][nextVisitedNode])
                    continue;

                visit[nextNode][nextVisitedNode] = true;
                queue.offer(new State(nextNode, nextVisitedNode));
            }
        }

        result++;
    }

    return -1;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能