Return to Answer

from collections import deque
def distancemetric(u, v, player, board):
 neighbors_u = neighborhood(u, player, board)
 dist = { u: 0 }
 dist.update({
 w: 1
 for w in neighbors_u
 })
 queue = deque(neighbors_u)
 visited = set()
 while queue: # BFS loop
 u = queue.popleft()
 for w in neighborhood(u, player, board):
 if w not in dist:
 if w in visited: # second path found
 dist[w] = dist[u] + 1
 if w == v:
 return dist[v]
 queue.append(w)
 else: # first path found
 visited.add(w)
 return math.inf

from collections import deque
def distancemetric(u, v, player, board):
 neighbors_u = neighborhood(u, player, board)
 if v in neighbors_u:
 return 1 # for distance 1
 dist = { u: 0 }
 dist.update({
 w: 1
 for w in neighbors_u
 })
 queue = deque(neighbors_u)
 visited = set()
 while queue: # BFS loop
 u = queue.popleft()
 for w in neighborhood(u, player, board):
 if w not in dist:
 if w in visited: # second path found
 dist[w] = dist[u] + 1
 if w == v:
 return dist[v]
 queue.append(w)
 else: # first path found
 visited.add(w)
 return math.inf

Depth-first search is not the ideal approach when the goal is a shortest path, even when you need 2 shortest alternatives at each step. The problem with your DFS implementation is that you could get into a dead end when all neighboring cells were on the path that led you to that cell. In that situation, you return infinity as value, but that will not be the true value of that cell if its neighborhood were free from visited cells. So infinity gets assigned (and memoized) to cells from which the target could really be reached. For instance, if in your example you swap u and v, looking for the distance in opposite direction, you'll get infinity.

Another interesting aspect is that in your recursive solution, you'll first assign distances to the cells closest to the target and then assign other distances as you unwind from recursion. But this solves the opposite problem from what is in the paper for that example. In the paper, the distances are assigned in forward way, as from u, not on the way "out" as distances to v.

Related to this, the distance formula is not consistent for paths in the opposite direction. If you would start from (4, 1) and find the shortest distance to black's virtual starting point, you'd get a different distance (4).

Ignoring that surprising property, BFS will work better here.

Also, performing a loop for increasing k is not that efficient. Instead, assign a distance to a cell when you have found the second shortest path (via another neighboring cell).

Here is an implementation:

def distancemetric(u, v, player, board):
 neighbors_u = neighborhood(u, player, board)
 dist = { u: 0 }
 dist.update({
 w: 1
 for w in neighbors_u
 })
 queue = list(neighbors_u)
 visited = set()
 while queue: # BFS loop
 u = queue.pop(0)
 for w in neighborhood(u, player, board):
 if w not in dist:
 if w in visited: # second path found
 dist[w] = dist[u] + 1
 if w == v:
 return dist[v]
 queue.append(w)
 else: # first path found
 visited.add(w)
 return math.inf

Depth-first search is not the ideal approach when the goal is a shortest path, even when you need 2 shortest alternatives at each step. The problem with your DFS implementation is that you could get into a dead end when all neighboring cells were on the path that led you to that cell. In that situation, you return infinity as value, but that will not be the true value of that cell if its neighborhood were free from visited cells. So infinity gets assigned (and memoized) to cells from which the target could really be reached. For instance, if in your example you swap u and v, looking for the distance in opposite direction, you'll get infinity.

Another interesting aspect is that in your recursive solution, you'll first assign distances to the cells closest to the target and then assign other distances as you unwind from recursion. But this solves the opposite problem from what is in the paper for that example. In the paper, the distances are assigned in forward way, as from u, not on the way "out" as distances to v.

Related to this, the distance formula is not consistent for paths in the opposite direction. If you would start from (4, 1) and find the shortest distance to black's virtual starting point, you'd get a different distance (4).

Ignoring that surprising property, BFS will work better here.

Also, performing a loop for increasing k is not that efficient. Instead, assign a distance to a cell when you have found the second shortest path (via another neighboring cell).

Here is an implementation:

from collections import deque
def distancemetric(u, v, player, board):
 neighbors_u = neighborhood(u, player, board)
 dist = { u: 0 }
 dist.update({
 w: 1
 for w in neighbors_u
 })
 queue = deque(neighbors_u)
 visited = set()
 while queue: # BFS loop
 u = queue.popleft()
 for w in neighborhood(u, player, board):
 if w not in dist:
 if w in visited: # second path found
 dist[w] = dist[u] + 1
 if w == v:
 return dist[v]
 queue.append(w)
 else: # first path found
 visited.add(w)
 return math.inf