Given a undirected connected graph, get the shortest distance from any node to any node and make sure every node is visited at least once. This is a pretty classic state compress dp problem. We can use a mask and a number representing which nodes are visited and which node is the last in the path. Also, configuration map BFS can be applied by using similar state as a condition.
n = len(graph)
for i in range(n):
graph[i] = set(graph[i]) # quick search, doesn't matter much
dp = [[1e9]*n for _ in range(1<<n)]
for i in range(n): # initialization
dp[1<<i][i] = 0
for i in range(1<<n):
# update the current state
for j in range(n):
for k in range(n):
if k != j and i & (1<<j) and i & (1<<k) and k in graph[j]:
dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + 1)
# update the next state
for j in range(n):
for k in range(n):
if k != j and i & (1<<j) and (i & (1<<k) == 0) and k in graph[j]:
dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k], dp[i][j] + 1)