algorithm - 查找从节点 A 到节点 B 的最小成本并保留路径信息

Question

我有一个问题是找到从最小节点 (1) 到最大节点 (7) 的最小成本。

成本是节点之间的边。我给它们贴上了标签。

这个问题让我想到了 Dijkstra，它导致 O((v+e) log v)

的时间复杂度

还有其他更好的方法可以有效地解决这个问题吗？

另外一个要求就是保留路径信息，有没有想过保留路径的？

Answer 1

正如其他人指出的那样，复杂性如您所说，再好不过了。正如@nico-schertler 评论的那样，从两侧并行(或轮流)搜索并在接触到某物时立即停止比仅从一侧进行搜索更快，但它具有相同的复杂性。在这种情况下是可能的(双向边的成本是固定的)，但在 Dijkstra 仍然适用的一般情况下(例如，成本取决于已经采用的路径)不需要。

关于路径的保持:当然，通常只有当你得到路径作为答案时，整个事情才有意义。有两种主要方法可以获取路径结果。

一种是将已经到达某个节点的路径与列表中的节点一起存储(在经典实现中为白色/灰色)。每次添加新节点时，都会将其前一个节点的路径扩展一步。如果找到目标节点，则可以直接返回路径作为结果(连同成本总和)。当然这种方式意味着使用大量内存。

另一个是不将原始节点与每个新发现的节点一起存储，因此每个节点都指向它首先访问的节点。可以把它想象成在每个节点上放置路标如何返回。这样，如果找到目标节点，则必须从每个节点向后返回到它第一次访问的节点，并在此过程中以相反的顺序构建路径。然后你可以返回这个路径。