Dijksta算法中为什么记录最短路径时只记录自己的直接前驱,而不是整个最短路径的顶点序列
时间: 2024-02-29 07:54:11 浏览: 13
Dijkstra算法是一种单源最短路径算法,它的目的是找到从起点到所有其他顶点的最短路径。在该算法中,我们需要记录每个顶点的最短路径以及其直接前驱。
当我们在计算出某个顶点的最短路径后,我们只需要记录该顶点的直接前驱,因为该前驱是该顶点最短路径上的最后一个顶点。这样,我们可以通过回溯每个顶点的直接前驱,从而得到从起点到该顶点的最短路径。因此,只记录直接前驱足以得到整个最短路径的顶点序列,而不需要记录整个路径的顶点序列。
此外,记录整个最短路径的顶点序列可能会占用更多的空间,而只记录直接前驱可以节省空间。因此,只记录直接前驱是Dijkstra算法的一个优化。