如果我知道每两个顶点之间的所有最短距离，但不知道最短生成树，则找到最短路径

Question

我有一个有向图G =（V，E），并且具有非负边权重，并且我知道从源顶点s到G中所有其他顶点的最短路径距离d（s，u）。但是，我没有最短路径树。我如何设计线性时间算法，以找到从s到给定顶点t的最短路径。

Answer 1

这显然是家庭作业，所以我不会给出答案。但这是一个很大的提示：

大概您已经熟悉A *。看一下算法，问一下自己如果使用的启发式是perfect，则哪些步骤是不必要的。然后确定（仅从问题中）给出d（t）以及到目前为止我们已经看过的节点，确定如何找到理想的启发式h（t）。

您可能需要对此思考一下[[向后

...

Answer 2

我有一个幼稚的主意，但您可以尝试。