Dijkstras算法 - 父节点？

Question

我的教授希望我们将它实现为网络中所有其他节点的单个源节点。他说通过使用父节点跟踪最短路径，但我不知道这在算法上下文中意味着什么。

我可以或多或少地正确实施我的代码，因为我的输出距离对于我运行的任何网络都是正确的。

但是，大多数在线资源都会讨论访问节点，并在探索所有相邻节点时将其标记为已访问节点。因此，例如，如果节点A和B与节点C相邻，并且与A的新距离小于B的距离，那么是否标记访问了节点C？然后，如果我到达节点A并意识到它导致我下降的路径实际上会导致已经记录的距离实际上更大，会发生什么？

Answer 1

为了从Dystra的算法中获得一条路径（而不仅仅是一个成本），而不是节省每个节点的最佳成本，保存这对（best_cost，from_where）。 from-where是生成best_cost的相邻节点的句柄。

然后，您可以沿着from_where指针返回原点以获得最佳路径。我怀疑“父母”是他的2元组/对中from_where元素的名字。

Answer 2

我的教授希望我们将它实现为网络中所有其他节点的单个源节点。他说通过使用父节点来跟踪最短路径，但我不知道这在算法的上下文中意味着什么。

那么，这就是说，对于每个节点，您存储哪个节点是它来自的最短路径中的节点。这样，一旦完成算法，就可以按照相反的顺序走最短路径，不仅可以找到最短路径的距离，还可以找到最短路径本身。

但是，大多数在线资源都会谈论访问节点，并且在您探索所有相邻节点时将其标记为访问节点。

您标记了一个访问节点后，它是最低距离的未访问节点。除非存在负距离，否则您将无法找到距离较短的路径（即使如此，如果图形的距离低于零，则只是一个问题）。