比方说,我有一个简单的图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。
鉴于此,我还想找到一种有效的方法来存储从B到D以及从C到D的距离,而BFS算法遍历该图(从A开始到D结束)。我更喜欢将BFS与备忘录/动态编程等功能结合使用。
PS:我的BFS实现确定在从队列中弹出v后 的每个顶点v的邻居。因此,不可能在图表中倒退,即从D到A。
从A到D的距离与在反转所有圆弧的方向后从D到A的距离相同。只需构建一个转置图,然后从D运行BFS,直到到达每个节点并记录距离。一些伪代码如下所示:
distances = {}
visited = {source_node}
frontier = queue([(target_node,0)])
while !frontier.empty():
node,distance = frontier.pop()
distances[node] = distance
for nei in node.neighbors:
if nei not in visited:
frontier.push((nei,distance + 1))
visited.insert(nei)
最后,您将获得一个地图distances
,其中distances[node]
是从node
到目标顶点的距离。
请注意,在BFS中,您不需要向后移动。向后走永远不会找到最短的路径,因为您要增加到达每个目标的距离。