bfs.append((next_state, next_step))

step+=1

flip+=1

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

classSolution:

defladderLength(self,beginWord:str,endWord:str,wordList: List[str]) ->int:

N, K=len(wordList),len(beginWord)

find_end=False

for iinrange(N):

if wordList[i]== endWord:

find_end=True

ifnot find_end:

wordList.append(beginWord)

N+=1

cluster= collections.defaultdict(list)

for iinrange(N):

node= wordList[i]

for jinrange(K):

cluster[node[:j]+'*'+ node[j+1:]].append(node)

visited_start, visited_end=set([beginWord]),set([endWord])

bfs_start, bfs_end= collections.deque([beginWord]), collections.deque([endWord])

step=2

while bfs_startand bfs_end:

num_level=len(bfs_start)

while num_level>0:

node= bfs_start.popleft()

for jinrange(K):

key= node[:j]+'*'+ node[j+1:]

for nin cluster[key]:

if nin visited_end:# if meet, route from start larger by 1 than route from end

return step*2-2

if nnotin visited_start:

visited_start.add(n)

bfs_start.append(n)

num_level-=1

num_level=len(bfs_end)

while num_level>0:

node= bfs_end.popleft()

for jinrange(K):

key= node[:j]+'*'+ node[j+1:]

for nin cluster[key]:

if nin visited_start:# if meet, route from start equals route from end

return step*2-1

if nnotin visited_end:

visited_end.add(n)

bfs_end.append(n)

num_level-=1

step+=1

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

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