shortest_path.md

最短路径问题

BFS

在处理不带权图的最短路径问题时可以使用 BFS。

walls-and-gates

给定一个二维矩阵，矩阵中元素 -1 表示墙或是障碍物，0 表示一扇门，INF (2147483647) 表示一个空的房间。你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。

• 思路：典型的多源最短路径问题，将所有源作为 BFS 的第一层即可

inf=2147483647classSolution:
defwallsAndGates(self, rooms: List[List[int]]) ->None:
""" Do not return anything, modify rooms in-place instead. """ifnotroomsornotrooms[0]:
returnM, N=len(rooms), len(rooms[0])
bfs=collections.deque([])
foriinrange(M):
forjinrange(N):
ifrooms[i][j] ==0:
bfs.append((i, j))
dist=1whilebfs:
num_level=len(bfs)
for_inrange(num_level):
r, c=bfs.popleft()
ifr-1>=0androoms[r-1][c] ==inf:
rooms[r-1][c] =distbfs.append((r-1, c))
ifr+1<Mandrooms[r+1][c] ==inf:
rooms[r+1][c] =distbfs.append((r+1, c))
ifc-1>=0androoms[r][c-1] ==inf:
rooms[r][c-1] =distbfs.append((r, c-1))
ifc+1<Nandrooms[r][c+1] ==inf:
rooms[r][c+1] =distbfs.append((r, c+1))
dist+=1return

shortest-bridge

在给定的 01 矩阵 A 中，存在两座岛 (岛是由四面相连的 1 形成的一个连通分量)。现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。返回必须翻转的 0 的最小数目。

• 思路：DFS 遍历连通分量找边界，从边界开始 BFS找最短路径

classSolution:
defshortestBridge(self, A: List[List[int]]) ->int:
M, N=len(A), len(A[0])
neighors= ((-1, 0), (1, 0), (0, -1), (0, 1))
dfs= []
bfs=collections.deque([])
foriinrange(M):
forjinrange(N):
ifA[i][j] ==1: # start from a 1dfs.append((i, j))
breakifdfs:
breakwhiledfs:
r, c=dfs.pop()
ifA[r][c] ==1:
A[r][c] =-1fordr, dcinneighors:
nr, nc=r+dr, c+dcif0<=nr<Mand0<=nc<N:
ifA[nr][nc] ==0: # meet and edgeA[nr][nc] =-2bfs.append((nr, nc))
elifA[nr][nc] ==1:
dfs.append((nr, nc))
flip=1whilebfs:
num_level=len(bfs)
for_inrange(num_level):
r, c=bfs.popleft()
fordr, dcinneighors:
nr, nc=r+dr, c+dcif0<=nr<Mand0<=nc<N:
ifA[nr][nc] ==0:
A[nr][nc] =-2bfs.append((nr, nc))
elifA[nr][nc] ==1:
returnflipflip+=1

Dijkstra's Algorithm

用于求解单源最短路径问题。思想是 greedy 构造 shortest path tree (SPT)，每次将当前距离源点最短的不在 SPT 中的结点加入SPT，与构造最小生成树 (MST) 的 Prim's algorithm 非常相似。可以用 priority queue (heap) 实现。

network-delay-time

• 标准的单源最短路径问题，使用朴素的 Dijikstra 算法即可。

classSolution:
defnetworkDelayTime(self, times: List[List[int]], N: int, K: int) ->int:
# construct graphgraph_neighbor=collections.defaultdict(list)
fors, e, tintimes:
graph_neighbor[s].append((e, t))
# DijkstraSPT= {}
min_heap= [(0, K)]
whilemin_heap:
delay, node=heapq.heappop(min_heap)
ifnodenotinSPT:
SPT[node] =delayforn, dingraph_neighbor[node]:
ifnnotinSPT:
heapq.heappush(min_heap, (d+delay, n))
returnmax(SPT.values()) iflen(SPT) ==Nelse-1

cheapest-flights-within-k-stops

• 在标准的单源最短路径问题上限制了路径的边数，因此需要同时维护当前 SPT 内每个结点最短路径的边数，当遇到边数更小的路径 (边权和可以更大) 时结点需要重新入堆，以更新后继在边数上限内没达到的结点。

classSolution:
deffindCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) ->int:
# construct graphgraph_neighbor=collections.defaultdict(list)
fors, e, pinflights:
graph_neighbor[s].append((e, p))
# modified Dijkstraprices, steps= {}, {}
min_heap= [(0, 0, src)]
whilelen(min_heap) >0:
price, step, node=heapq.heappop(min_heap)
ifnode==dst: # early returnreturnpriceifnodenotinprices:
prices[node] =pricesteps[node] =stepifstep<=K:
step+=1forn, pingraph_neighbor[node]:
ifnnotinpricesorstep<steps[n]:
heapq.heappush(min_heap, (p+price, step, n))
return-1

补充

Bidrectional BFS

当求点对点的最短路径时，BFS遍历结点数目随路径长度呈指数增长，为缩小遍历结点数目可以考虑从起点 BFS 的同时从终点也做 BFS，当路径相遇时得到最短路径。

word-ladder

classSolution:
defladderLength(self, beginWord: str, endWord: str, wordList: List[str]) ->int:
N, K=len(wordList), len(beginWord)
find_end=Falseforiinrange(N):
ifwordList[i] ==endWord:
find_end=Truebreakifnotfind_end:
return0wordList.append(beginWord)
N+=1# clustering nodes for efficiency compare to adjacent listcluster=collections.defaultdict(list)
foriinrange(N):
node=wordList[i]
forjinrange(K):
cluster[node[:j] +'*'+node[j+1:]].append(node)
# bidirectional BFSvisited_start, visited_end=set([beginWord]), set([endWord])
bfs_start, bfs_end=collections.deque([beginWord]), collections.deque([endWord])
step=2whilebfs_startandbfs_end:
# startnum_level=len(bfs_start)
whilenum_level>0:
node=bfs_start.popleft()
forjinrange(K):
key=node[:j] +'*'+node[j+1:]
fornincluster[key]:
ifninvisited_end: # if meet, route from start larger by 1 than route from endreturnstep*2-2ifnnotinvisited_start:
visited_start.add(n)
bfs_start.append(n)
num_level-=1# endnum_level=len(bfs_end)
whilenum_level>0:
node=bfs_end.popleft()
forjinrange(K):
key=node[:j] +'*'+node[j+1:]
fornincluster[key]:
ifninvisited_start: # if meet, route from start equals route from endreturnstep*2-1ifnnotinvisited_end:
visited_end.add(n)
bfs_end.append(n)
num_level-=1step+=1return0

A* Algorithm

当需要求解有目标的最短路径问题时，BFS 或 Dijkstra's algorithm 可能会搜索过多冗余的其他目标从而降低搜索效率，此时可以考虑使用 A* algorithm。原理不展开，有兴趣可以自行搜索。实现上和 Dijkstra’s algorithm 非常相似，只是优先级需要加上一个到目标点距离的估值，这个估值严格小于等于真正的最短距离时保证得到最优解。当 A* algorithm 中的距离估值为 0 时 退化为 BFS 或 Dijkstra’s algorithm。

sliding-puzzle

• 方法 1：BFS。为了方便对比 A* 算法写成了与其相似的形式。

classSolution:
defslidingPuzzle(self, board: List[List[int]]) ->int:
next_move= {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4]
}
start=tuple(itertools.chain(*board))
target= (1, 2, 3, 4, 5, 0)
target_wrong= (1, 2, 3, 5, 4, 0)
SPT=set()
bfs=collections.deque([(0, start, start.index(0))])
whilebfs:
step, state, idx0=bfs.popleft()
ifstate==target:
returnstepifstate==target_wrong:
return-1ifstatenotinSPT:
SPT.add(state)
fornext_stepinnext_move[idx0]:
next_state=list(state)
next_state[idx0], next_state[next_step] =next_state[next_step], next_state[idx0]
next_state=tuple(next_state)
ifnext_statenotinSPT:
bfs.append((step+1, next_state, next_step))
return-1

• 方法 2：A* algorithm

classSolution:
defslidingPuzzle(self, board: List[List[int]]) ->int:
next_move= {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4],
4: [1, 3, 5],
5: [2, 4]
}
start=tuple(itertools.chain(*board))
target, target_idx= (1, 2, 3, 4, 5, 0), (5, 0, 1, 2, 3, 4)
target_wrong= (1, 2, 3, 5, 4, 0)
@functools.lru_cache(maxsize=None)deftaxicab_dist(x, y):
returnabs(x//3-y//3) +abs(x%3-y%3)
deftaxicab_sum(state, t_idx):
result=0fori, numinenumerate(state):
result+=taxicab_dist(i, t_idx[num])
returnresultSPT=set()
min_heap= [(0+taxicab_sum(start, target_idx), 0, start, start.index(0))]
whilemin_heap:
cur_cost, step, state, idx0=heapq.heappop(min_heap)
ifstate==target:
returnstepifstate==target_wrong:
return-1ifstatenotinSPT:
SPT.add(state)
fornext_stepinnext_move[idx0]:
next_state=list(state)
next_state[idx0], next_state[next_step] =next_state[next_step], next_state[idx0]
next_state=tuple(next_state)
next_cost=step+1+taxicab_sum(next_state, target_idx)
ifnext_statenotinSPT:
heapq.heappush(min_heap, (next_cost, step+1, next_state, next_step))
return-1