我有一个无向图'G'，并且在图G中有一组节点'A'
我正在努力寻找一种有效的算法，该算法可以找到从图G中的任何节点到集合'A'中最近的节点的最短路径
我考虑过这一点：拥有一个到所有节点的最小距离数组，在集合A中的每个节点上运行BFS算法，并且在BFS完成之后，如果找到了更短的路径，则更新数组，这时的复杂度为O（k（n + m））-随着K的增加，很多时候我被告知我可以使用更有效的算法。请注意，本练习只允许我使用BFS算法
pu1188 回答：我如何找到从任何节点到集合A的最短路径
创建一个额外的节点，该节点的'A'中的每个节点都具有边缘。从这个额外的节点运行BFS。每个节点到“ A”中最近的节点的距离比到此额外节点的距离小1。
,如果您从初始队列中A的所有节点开始，实际上只需要一次传递BFS算法。
- 在地图/字典中跟踪已访问节点及其从A到节点的路径
- 为
(a,empty_path)中的每个节点a用元组A初始化BFS队列 - 当队列中有更多元素时，从队列中弹出下一个节点和路径
- 如果该节点已经在
visited映射中，请跳过它 - 否则，将其添加到具有给定路径的
visited - 将具有扩展路径的邻居节点添加到队列
Python示例：
# 2--0--1
# | |
# 3 4
graph = {0: [1,2],1: [0,4],2: [0,3],3: [2],4: [1]}
A = [2,0]
import collections
queue = collections.deque([(a,[]) for a in A])
visited = {}
while queue:
cur,path = queue.popleft()
if cur in visited: continue
visited[cur] = path
for node in graph[cur]:
queue.append((node,[cur] + path))
print(visited)
# {2: [],0: [],1: [0],4: [1,0]}