847. Shortest Path Visiting All Nodes

You have an undirected, connected graph of n nodes labeled from 0 to n - 1. You are given an array graph where graph[i] is a list of all the nodes connected with node i by an edge.

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

Constraints:

• 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] contains a.

• The input graph is always connected.

Solution

When encountering a shorted path/smallest cost problem, the first idea that comes to my mind is BFS. The difference is that if the edges are weighted, we use Dijkstra, (PrioirtyQueue), otherwise, we use BFS.

With BFS, we can guarantee the first happen that satisfied our requirement (i.e visited all nodes) will be the shortest one.

However, this problem is not that easy... Because we can visit a node any number of times And we can get rid of the visited node checking. The avoidance of cycles is essential in BFS too.

So, for any node visiting, we must not only record if a node is visited, we need a macro information. -- the visited status of the current path. We kept the visitedStatus and currentPosition, and form them into a state data structure..

class State{
    int curPosistion;
    int visitedStatus; //bitOperation for all nodes
}

If the current state has happened before. We must get rid of it.

Now we can solve it with an enhanced BFS.

public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    Queue<State> queue = new LinkedList<>();
    Set<String> set = new HashSet<>();
    int status = 0;
    for(int i = 0; i < n; i++) {
        status |= (1<<i);
        queue.add(new State((1<<i), i, 0));
        set.add(status+":"+i);
        status = 0;
    }
    while(!queue.isEmpty()) {
        State s = queue.poll();
        if(s.visitedStatus == (1 << n) -1){
            return s.cost;
        }
        s.cost++;
        for(int next : graph[s.curPosition]){
            status = s.visitedStatus | (1 << next);
            if(!set.contains(status+":"+next)){
                set.add(status+":"+next);
                queue.add(new State(status, next, s.cost));
            }
        }
    }
    return -1;
}

class State{
    int visitedStatus = 0;
    int curPosition = 0;
    int cost = 0;
    public State(int status, int position, int cost){
        this.visitedStatus = status;
        this.curPosition = position;
        this.cost = cost;
    }
}