algorithm - 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

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

好吧，这只是意味着对于每个节点，您将哪个节点存储在它的最短路径中。这样，一旦你完成了你的算法，你就可以以相反的顺序走最短路径，不仅可以找到最短路径的距离，还可以找到最短路径本身。

但是大多数在线资源都在讨论访问节点，并在您探索所有相邻节点后将它们标记为已访问。

在它是距离最短的未访问节点之后标记已访问的节点。除非存在负距离，否则您将无法找到距离更短的路径（即使那样，如果您的图表有一个距离小于零的循环，这只是一个问题）。