algorithm - 如何找到从任何节点到集合 A 的最短路径

Question

我在图 G 中有一个无向图“G”和一组节点“A”

我正在努力寻找一种有效的算法，该算法可以找到从图 G 中的任何节点到集合“A”中最近节点的最短路径

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

Answer 1

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