使用BFS，有没有一种方法可以找到从所有顶点到目标顶点的距离？

Question

假设我有一个简单的图A-> B-> C->D。边权重均为1。A是起始顶点，D是目标顶点。使用BFS，我可以轻松确定从A到D的距离为3。

鉴于此，我还想找到一种有效的方法来存储从B到D以及从C到D的距离，而BFS算法遍历该图（从A开始到D结束）。我更喜欢将BFS与备忘录/动态编​​程等功能结合使用。

PS：我对BFS的实现确定了每个顶点v的邻居。之后

v从队列中弹出。因此，不可能在图表中向后移动，即从D到A。

假设我有一个简单的图A-> B-> C->D。边权重均为1。A是起始顶点，D是目标顶点。使用BFS，我可以轻松确定从A到D的距离是3。...

Answer 1

从A到D的距离与从D到A的距离相同。只需构建一个转置图，然后从D运行BFS，直到到达每个节点并记录距离。一些伪代码如下所示：