我怎样才能找到从任何节点到集合 A 的最短路径

Question

我有一个无向图 'G' 和图 G

中的一组 'A' 节点

我正在努力寻找一种有效的算法来找到从图 G 中的任何节点到集合中最近的节点的最短路径 'A'

我想到了这个：有一个到所有节点的最小距离数组，运行集合 A 中的每个节点上的 BFS 算法，并且在 BFS 完成后，如果找到更短的路径则更新数组，这个时间复杂度是 O(k(n+m)) - 当 K 增长时很多，我被告知我可以使用更有效的算法。请注意，我只允许在本练习中使用 BFS 算法

Answer 1

创建一个额外的节点，该节点从这个额外的节点到 'A.' 运行 BFS 中的每个节点都有边。 'A' 中每个节点到最近节点的距离比到这个额外节点的距离小 1。

Answer 2

如果您从初始队列中 A 的所有节点开始，您真的只需要一次 BFS 算法。

在 map/dictionary
为您的A集合

a

(a, empty_path)

当队列中有更多元素时，从队列中弹出下一个节点和路径
如果该节点已经在 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: [], 3: [2], 1: [0], 4: [1, 0]}

我怎样才能找到从任何节点到集合 A 的最短路径

How can i find the shortest path from any node to a set A

algorithm

data-structures

graph

shortest-path