algorithm - "uniform-cost search"算法中的路径如何获取？

Question

我一直在研究统一成本搜索的算法，尽管我能够理解整个优先级队列过程，但我无法理解算法的最后阶段。

如果我们看at this graph ，在应用该算法后，我将得到每个节点的最小距离，但假设我想知道 A 到 G 之间的路径(就像示例一样)，我将如何计算它？

Answer 1

通常，您从尚未探索的每个节点的无限总成本开始。然后你可以稍微调整一下算法来保存前身:

for each of node's neighbours n
    if n is not in explored
        if n is not in frontier
            frontier.add(n)
            set n's predecessor to node
        elif n is in frontier with higher cost
            replace existing node with n
            set n's predecessor to node

之后，您可以从您的目标开始，检查前辈的顺序。