跳到内容
从一个困惑开始

你想弄懂什么?

找到答案,看到讲解发生的那一刻,再顺着概念继续探索。

← 概念导览

关于「运行 Dijkstra 算法后,如何重建从家到大学的最短路径?」

4 个关键词匹配

正在理解你的问题,下面的搜索结果可先查看。

掌握方法

↗

要重建最短路径,你需要从目标顶点沿着前驱箭头向后追溯到源顶点。在算法执行期间,每当选择一个顶点或更新其标签时,都会从提供当前最佳标签的顶点画出一个箭头。

适用条件:在前驱箭头必须在标签更新期间被记录下来。;目标标签已经最终确定(被圈出)。;图是有向的,或者为了遵循记录的箭头而被视为有向的。

认识概念

↗

从家到大学的最终最短距离是 7。该值是在处理完所有更小的未圈出候选值(特别是标签为 4 的顶点 E 和标签为 6 的顶点 B)之后确定的。

适用条件:算法已经处理了所有暂定标签小于 7 的顶点。;大学处的标签 7 是剩余的最小未圈出标签。;图中的边权重固定为示例中所示。

掌握方法

↗

当一个顶点从不同路径接收到多个距离计算时,你只保留最小的值并划掉较大的值。这确保顶点的标签始终代表从源出发的最短已知距离。

适用条件:顶点可以通过来自不同圈出顶点的多条路径到达。;对已标记的顶点执行新的距离计算。

认识概念

↗

顶点处的数字标签代表从源顶点(家)到该特定顶点的当前已知最佳距离。标签周围的蓝色圆圈表示该距离在当前算法运行中已被接受为该顶点的最终值。

适用条件:演示使用视觉白板式的表示法。;源顶点是“家”。;算法是 Dijkstra 最短路径算法。