Problem statement

https://leetcode.com/problems/shortest-path-visiting-all-nodes/

Solution

Let us first find distances between all pairs of nodes, using either bfs or better Floyd-Warshall algorithm with O(n^3) complexity. (do not be afraid of this algorithm, in fact it is just usual dp, but it is not the point of interest here, we want to focus on dp on subsets.

Then our problem is equivalent to Traveling Salesman Problem (TSP): we need to find path with smallest weight, visiting all nodes. Here we have 2^n * n possible states, where state consists of two elements:

  1. mask: binary mask with length n with already visited nodes.
  2. last: last visited node.

Note, that it is wary similar to previous approach we used, but now we need to include last visited node in our state.

Complexity

There will be O(n) possible transitions for each state: for example to the state (10011101, 7) we will have possible steps from (00011101, 0), (00011101, 2), (00011101, 3), (00011101, 4). Finally, time complexity is O(2^n*n^2) and space complexity is O(2^n*n).

Code

class Solution:
    def shortestPathLength(self, graph):
        n = len(graph)
        W = [[float("inf")] * n for _ in range(n)]
        #for i in range(n): W[i][i] = 0
        for i in range(n):
            for j in graph[i]:
                W[i][j] = 1
        
        for i,j,k in product(range(n), repeat = 3):
            W[i][j] = min(W[i][j], W[i][k] + W[k][j])
                    
        dp = [[float("inf")] * n for _ in range(1<<n)]
        for i in range(n): dp[1<<i][i] = 0
            
        for mask in range(1<<n):
            n_z_bits = [j for j in range(n) if mask&(1<<j)]
            
            for j, k in permutations(n_z_bits, 2):
                cand = dp[mask ^ (1<<j)][k] + W[k][j]
                dp[mask][j] = min(dp[mask][j], cand)
        return min(dp[-1])