跳到内容
从一个困惑开始

你想弄懂什么?

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

← 概念导览

关于「为什么 Dijkstra 算法在目标标签 7 首次出现时不立即将其最终确定?」

6 个关键词匹配

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

理解原因

↗

算法不立即最终确定目标标签 7,因为仍有其他未圈出的顶点具有更小的暂定距离需要先处理。具体来说,顶点 E 有一个未圈出的标签 4,它小于 7。

适用条件:图正在由 Dijkstra 算法处理。;带有圈出标签的顶点被视为已选定/已确定。;未圈出的标签仍是暂定候选值。;存在至少一个未圈出的顶点,其标签小于目标的当前标签。

认识概念

↗

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

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

掌握方法

↗

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

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

认识概念

↗

初始化步骤涉及给起始顶点(家)分配距离 0,并通过在它周围画一个圆圈来将其标记为已访问。所有其他顶点最初都被认为具有无限或未定义的距离,直到它们被邻居计算更新。

适用条件:算法正在启动。;源顶点被识别为“家”。

认识概念

↗

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

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

认识概念

↗

规则是选择具有最小暂定距离标签的未圈出顶点。然后圈出该顶点以将其标记为已确定,并从提供此最小距离的顶点画出前驱箭头。

适用条件:有分配了距离标签的未圈出顶点。;算法在更新邻居后处于选择阶段。