对Dijkstra的最短路径和MST感到困惑

Question

Dijkstra的最短路径算法应该像我在教科书中介绍算法那样返回一棵树吗？在我看到的在线示例中，它只显示了两个顶点之间的最短路径。在我的教科书中，它返回一个树，边缘连接到每个顶点。我糊涂了。

Answer 1

这取决于你正在使用的教科书：Dijkstra的算法解决了单源最短路径问题，并且如果你正在计算这些路径或它们的长度，那么将每个顶点的前任存储在最短路径中并不是很多额外的工作。因此，根据来源和应用程序，您可能会阅读以下内容：

• DijkstraParents（G，s），它返回从s到图G中任何其他顶点的最短路径中每个顶点的父节点;
• DijkstraTree（G，s），它可以使用DijkstraParents（G，s）的结果返回实际的最短路径树;
• DijkstraPath（G，s，t），它可以使用DijkstraParents（G，s）或DijkstraTree（G，s）的结果显式地返回从s到t的最短路径;
• ...等等，包括使用上述计算纯粹的路径长度。

最后，所有这些版本都是主算法的微小变化，因此请使用适合您需求的版本。