Dijkstra算法（寻找最短路径）

1. 图示
   观察依据

   加权图中最左侧的顶点标记为“家”。

home

最短路径问题的起始顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   加权图中最右侧的顶点标记为“大学”。

university

最短路径问题的目标顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   图中的一个顶点标记为“A”。

A

网络中的一个中间顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   图中的一个顶点标记为“B”。

B

网络中的一个中间顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   图中的一个顶点标记为“C”。

C

网络中的一个中间顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   图中的一个顶点标记为“D”。

D

网络中的一个中间顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   图中的一个顶点标记为“E”。

E

网络中的一个中间顶点。

加权图中的一个顶点。

1. 图示
   观察依据

   最左侧的顶点标记为“家”，并标有带圆圈的值0。

home

最短路径计算的源顶点

所展示的带权图中的一个顶点

1. 图示
   观察依据

   最右侧的顶点标记为“大学”，随后依次获得候选标签7、9和8，最后得到带圆圈的最终标签7。

university

目标顶点，正在求其到“家”的最短距离

所展示的带权图中的一个顶点

1. 图示
   观察依据

   顶点A在视频片段开始时已用带圆圈的标签2标出。

2. 声音
   观察依据

   说话者在计算通往B和D的路径时，将A用作当前顶点。

A

从“家”出发已确定最短距离为2的中间顶点

所展示的带权图中的一个顶点

1. 图示
   观察依据

   顶点B首先显示候选标签6，随后被标上带圆圈的6。

2. 声音
   观察依据

   我们可以从这里向上走到B，四加二是六。

B

一个中间顶点，其已确定的最短距离变为6

所显示的带权图中的一个顶点

1. 图示
   观察依据

   顶点C在片段开始时已用标签3标出并加圈。

C

一个中间顶点，其到起点（家）的已确定最短距离为3

所显示的带权图中的一个顶点

1. 声音
   观察依据

   本视频将介绍戴克斯特拉算法，这是一种系统化的方法，用于确定网络中从一个顶点到另一个顶点的最短路径。

一种用于在加权网络中寻找两个顶点之间最短路径的系统化方法。

1. 该网络的边权重必须为非负数。

1. 声音
   观察依据

   首先，我们在‘家’顶点旁标注数字零，因为该顶点到‘家’的距离为零，并将该顶点用圆圈标出。

2. 动画
   观察依据

   一个蓝色的‘0’写在‘家’顶点旁，并用蓝色圆圈将其围住。

将距离‘0’赋给起始顶点，并将其标记为已访问（即用圆圈标出）。

1. 适用于路径的起始顶点。

1. 戴克斯特拉算法

1. 声音
   观察依据

   接下来，在每一步中，我们观察已被圆圈标出的顶点，并找出其尚未被圆圈标出的邻接顶点。因此我们可以到达顶点 A，距离为二；也可以到达顶点 C，距离为三。

2. 动画
   观察依据

   蓝色数字‘2’和‘3’分别写在顶点 A 和顶点 C 旁。

对于当前已被圆圈标出的顶点，将其到各未访问邻接顶点的总距离计算出来——即该顶点的距离加上对应边的权重，并将这些新距离标注在相应邻接顶点旁。

1. 仅适用于尚未被圆圈标出的邻接顶点。

1. 初始化步骤

1. 声音
   观察依据

   现在我们寻找图中所有已写出但尚未被圆圈标出的最小数字。本例中该数为二，因此我们将它用圆圈标出，并画出一个箭头，指示该数值的来源——它来自‘家’。

2. 动画
   观察依据

   顶点 A 处的数字2被画圈，同时从“起点”向 A 画一条蓝色箭头。

在所有未画圈的顶点中，找出距离最小的那个；将该顶点画圈，并从它的前驱顶点向它画一条箭头，以记录最短路径。

1. 当存在已赋值但尚未画圈的顶点时，此步骤适用。

1. 更新邻接顶点

1. 声音
   观察依据

   每当某个顶点上有两个或更多数字时，我们就划掉所有不等于最小值的数字。因此，在这个例子中，C 处有三和四，所以我们只需划掉那个四。

2. 动画
   观察依据

   顶点 C 处的数字4被一条蓝色直线划掉。

若某顶点收到多个距离计算结果，则仅保留最小值，其余较大的值全部划掉。

1. 当某顶点可通过来自不同已画圈顶点的多条路径到达时，便会出现这种情况。

1. 更新邻接顶点

1. 声音
   观察依据

   现在，我们不能仅因已得到七就断定它是最短距离，因为我们仍需考虑其他顶点。因此，最小的未加圆圈顶点是下方这个四。

2. 图示
   观察依据

   E 处的标号4在 university 处的标号7最终确定之前即被加圈。

该片段说明：目标顶点处的候选标号，须待其成为剩余未加圆圈标号中最小者时，才被视为最终标号。下一个被选中的顶点即为当前最小的未加圆圈顶点，此处是标号为4的 E。

1. 该图正由所展示的最短路径方法进行处理。

2. 标号已被加圈的顶点被视为已选定。

3. 未加圈的标签仍是候选值。

1. 本例题中数值顶点标签的含义

1. 图示
   观察依据

   数值标签在顶点处累积，并在整个图中进行比较。

2. 声音
   观察依据

   主讲人将标签解释为距离，例如“从家到B的距离是六”。

1. 视频从未用符号给出正式定义；本条目记录的是例题演示中可见的操作性含义。

在本次演示中，写在顶点旁的数字表示当前已知的从家到该顶点的最佳距离；加圈的数字表示该距离已在算法运行过程中被确认为该顶点的最终结果。

1. 适用于本片段中展示的具体白板式演示。

1. 声音
   观察依据

   “现在把这个圈起来，并标明它来自何处”

2. 图示
   观察依据

   箭头从A指向B、从C指向E、从D指向大学。

3. 声音
   观察依据

   “从大学往回推，我们来自D……D来自A……A来自家。”

每当一个顶点被选中或更新时，主讲人都会画出一条箭头，起点为提供当前最佳标签的那个顶点；随后通过反向追踪这些箭头来重构最短路径。

1. 当分配新的最优标签，或需要记录某个已选顶点的前驱顶点时使用。

1. 本例题中数值顶点标签的含义

1. 声音
   观察依据

   “现在最后我们得到这个七，它是未画圈顶点中最小的一个。”

2. 声音
   观察依据

   “这告诉我们，从家到大学的最短距离是七。”

3. 图示
   观察依据

   大学处的标签7被画圈，作为最后一个被选中的值。

在所有更小的未画圈候选顶点都被处理完毕后，大学处的标签7成为最小的未画圈顶点并被画圈。讲解者得出结论：从家到大学的最短距离是7。

1. 所有具有更小临时标签的相关顶点都已被处理完毕。

1. 在结束前，先选出最小的未加圆圈顶点
2. 本例题中数值顶点标签的含义

1. 声音
   观察依据

   “我们还可以推断出应走的路径。从大学开始逆向回溯：我们来自D……沿着指向D的箭头反向追溯，来自A……再从A继续反向追溯，来自家。”

2. 动画
   观察依据

   黄色高亮按逆序标出 university ← D ← A ← home。

1. “当你写出来时，它是”之后的口述句子被截断，未完成。

一旦目标顶点的标签被最终确定，实际路线便可通过从大学出发、反复沿所画箭头指示的前驱顶点移动而恢复。本例中的逆向链为 university ← D ← A ← home，由此得到正向路径 home → $A \to D$ → university。

1. 前驱箭头必须在标签更新过程中被记录下来。

1. 前驱箭头记录了生成该标签的路径。
2. 从家到大学的最短距离

1. 声音
   观察依据

   说话人解释从右向左回溯路径：“大学来自D，D来自A，A来自家。”

2. 图示
   观察依据

   黄色高亮的边表示从家到大学的路径。说话人在图下方写出序列“家 - A - D - 大学”。

在计算出到所有节点的最短距离后（通常使用戴克斯特拉等算法），可通过从目标节点回溯至源节点来找出实际的最短路径。每一步中，找出使距离最小化的前驱节点。

1. 所有节点的最短距离与前驱节点必须已预先计算完毕。

1. 声音
   观察依据

   说话人指出：“你还应标出该距离，且最短距离是七。”

2. 图示
   观察依据

   数字7写在最终路径序列旁。

在许多最短路径问题中，仅确定节点序列是不够的；还必须计算并报告该路径的总代价或总距离。这等于最短路径上所有边的权重之和。

1. 最短路径已经确定。

1. 最短路径算法中的路径回溯

1. 声音
   观察依据

   现在，我们不能仅凭已得到七这个数值就断定它是最短距离，因为我们仍需考虑其他顶点。

在此演示的戴克斯特拉算法运行过程中，当大学处出现候选距离7时，若仍存在更小的未加圈候选值，则不能立即终止算法。

1. 该图中包含多个未加圈的顶点。

2. 至少存在一个未加圈顶点，其标签值小于目标顶点当前的标签值。

对于当前展示的图状态，若存在某个未加圈顶点的标签小于目标顶点，则该目标顶点的标签尚未最终确定。

1. 声音
   观察依据

   如果从E到大学的边权仅为一或二，那么这实际上会为我们提供一条更短的路径。

1. 此处仅为假设性比较，并非对所展示图的实际修改。

若从E到大学的边权为1或2，则经由E的路径将产生比当前可见标签7更短的通往大学的路线。

1. E的已确定距离为4。

2. 当前考虑的边连接E与大学。

对于边权w(E, 大学) ∈ {1, 2}，所得候选距离$4 + w$小于7。

1. 声音
   观察依据

   这告诉我们，从家到大学的最短距离是七。

2. 图示
   观察依据

   大学处最终标出的数值是7。

对于视频片段中所示的带权图，从家到大学的最短距离是7。

1. 所显示的边权是固定的。

2. 该算法在此图上按演示方式应用。

对于所示的具体图实例，从家到大学的最短路径长度等于7。

1. 声音
   观察依据

   从大学往回追溯：我们来自D……D来自A……A来自家。

2. 动画
   观察依据

   黄色高亮标记了边家-A、A-D和D-大学。

例题所找出的最短路径是：家 → $A \to D$ → 大学。

1. 算法运行过程中记录的前驱箭头对于当前展示的运行过程是正确的。

针对图中所示的具体实例，重构出的最小化路径为：家 → $A \to D$ → 大学。

1. 声音
   观察依据

   因此我们可以前往 A，其距离为二；也可以前往 C，其距离为三。

2. 动画
   观察依据

   数字2和3分别出现在顶点 A 和 C 旁边。

1. 公式

   $$d(A) = d(home) + w(home, A) = 0 + 2 = 2$$
   解释

   计算从家到A的距离。

   步骤依据

   从家到A的边权为2。

   视频直接表达
2. 公式

   $$d(C) = d(home) + w(home, C) = 0 + 3 = 3$$
   解释

   计算从家到C的距离。

   步骤依据

   从家到C的边权为3。

   视频直接表达

到A和C的距离分别更新为2和3。

1. 声音
   观察依据

   因此，B是邻居，二加四等于六；D是邻居，二加二等于四；C是邻居，二加二等于四。

2. 动画
   观察依据

   数字6、4和4分别标在B、D和C旁边。

1. 公式

   $$d(B) = d(A) + w(A, B) = 2 + 4 = 6$$
   解释

   计算从A到B的距离。

   步骤依据

   从A到B的边权为4。

   视频直接表达
2. 公式

   $$d(D) = d(A) + w(A, D) = 2 + 2 = 4$$
   解释

   计算从A到D的距离。

   步骤依据

   从A到D的边权为2。

   视频直接表达
3. 公式

   $$d(C) = d(A) + w(A, C) = 2 + 2 = 4$$
   解释

   计算从A到C的另一条路径距离。

   步骤依据

   A到C的边权为2。

   视频直接表达

已计算出到B、D以及到C的另一条路径的距离。

1. 声音
   观察依据

   从刚刚圈出的这个顶点出发，我们可以到达A，但A的最短距离我们已经算出是二；不过我们确实可以到达E，三加一等于四。

2. 动画
   观察依据

   数字4标在E旁边。

1. 公式

   $$d(E) = d(C) + w(C, E) = 3 + 1 = 4$$
   解释

   计算从C到E的距离。

   步骤依据

   C到E的边权为1。

   视频直接表达

E的距离被更新为4。

1. 声音
   观察依据

   “好的，从那个点出发，我们可以向上走到B，四加二是六；可以走到大学，四加三是七；其他地方则无法到达。”

2. 图示
   观察依据

   在从A进行处理后，B处出现候选标签6，大学处出现候选标签7。

1. 开头语句不完整，但其中的算术运算及所得标签清晰明确。

1. 公式

   $$d(A)=2$$
   解释

   在视频片段开始时，顶点A已被圈出，且标有标签2。

   步骤依据

   观察到的图示状态。

   视频直接表达
2. 公式

   $$d(B)=d(A)+w(A,B)=2+4=6$$
   解释

   从A出发，讲解者为B计算出一个候选标签6。

   步骤依据

   音频中的算术运算结合A-B边上可见的边权4。

   视频直接表达
3. 公式

   $$d(\text{university})=d(A)+w(A,\text{university})=2+3=5$$
   解释

   利用A到大学边上可见的边权3，算得结果为5，但视频片段中实际显示并口述的是经由D路径所得的7。

   步骤依据

   图中显示边 A-大学 的权重为3，而语音说“四加三等于七”，大学处的书面候选值为7。

   视频直接表达
4. 公式

   $$d(\text{university})=d(D)+w(D,\text{university})=4+3=7$$
   解释

   大学处显示的候选值7对应经过 D 的路径，其中 D 的已确定标签为4，且 D 到大学的边权重为3。

   步骤依据

   D-大学之间可见的标签和边权重。

   依据视频推导

从 A 出发的处理在 B 处产生一个候选值6，而大学处可见的候选值7对应的是经由 D 的路径，而非直接从 A 出发的路径。

1. 声音
   观察依据

   “未加圈顶点中最小的是下面这个四”

2. 声音
   观察依据

   “观察 E，那里标着四，而它到大学的距离是九”

3. 图示
   观察依据

   E 被加圈并标上4，随后大学处写下9并划去与7的关联。

1. 公式

   $$\min\{\text{uncircled labels}\}=4 \text{ at } E$$
   解释

   在所有未加圈的顶点中，E 的标签最小。

   步骤依据

   语音明确指出“下面这个四”即为最小的未加圈顶点。

   视频直接表达
2. 公式

   $$d(E)=3+w(C,E)=3+1=4$$
   解释

   E 处的标签4来自 C，且 C 到 E 的边权重为1。

   步骤依据

   C 处可见的加圈标签为3，C-E 边上的权重为1，并有箭头 $C\to E$。

   依据视频推导
3. 公式

   $$d(\text{university})=d(E)+w(E,\text{university})=4+5=9$$
   解释

   从E出发，主讲人计算出一个大学的候选值9。

   步骤依据

   音频说“那是九到大学”，图中在大学处写有9。

   视频直接表达
4. 公式

   $$9>7$$
   解释

   新的候选值9比现有候选值7更差，因此将9划掉。

   步骤依据

   音频：“我们要划掉九，因为它不是最小的。”

   视频直接表达

E必须在目标节点之前被确定，因为它的出边可能改进目标节点的标签；在此图中，它产生9，该值被舍弃，转而采用7。

1. 声音
   观察依据

   “看起来在B处，我们这里有几个六。”

2. 声音
   观察依据

   “从B出发可以到达大学，六加二是八。”

3. 声音
   观察依据

   “我们这里有七和八，所以把八划掉。”

4. 图示
   观察依据

   B被圈出并标有6，大学处写有8但被划掉，随后7被圈出。

1. “这里有几个六”这一短语可听清，但复数形式的确切原因在该片段中未充分说明。

1. 公式

   $$d(B)=6$$
   解释

   处理完E后，剩余未圈出标签中最小的是B处的6，因此选择B。

   步骤依据

   音频指出B是下一个未加圈的最小顶点，图中在B处给6加圈。

   视频直接表达
2. 公式

   $$d(B)=d(A)+w(A,B)=2+4=6$$
   解释

   B处选定的标签6与之前从A出发的更新结果一致。

   步骤依据

   可见的标签及边A-B上的权重4。

   依据视频推导
3. 公式

   $$d(\text{university})=d(B)+w(B,\text{university})=6+2=8$$
   解释

   从B出发，主讲人计算出一个前往大学的候选值8。

   步骤依据

   音频说“六加二是八”，并在大学处写下8。

   视频直接表达
4. 公式

   $$8>7$$
   解释

   该候选值8比已有的候选值7更差，因此将8划掉。

   步骤依据

   音频：“把八划掉，因为它比七大。”

   视频直接表达
5. 公式

   $$d(\text{university})=7$$
   解释

   由于已无更小的未加圈候选值，大学处的标签7被加圈，作为最终结果。

   步骤依据

   音频：“现在，我们终于得到这个七，它是当前未加圈顶点中最小的。”图中对7加圈。

   视频直接表达

对B的处理无法改进目标，因为它给出的是8，因此此前已知的7成为最终的最短距离。

1. 声音
   观察依据

   “从大学反向追溯，我们来自D……沿D指向的箭头反向追溯，来自A……再沿A指向的箭头反向追溯，来自家。”

2. 动画
   观察依据

   黄色高亮依次出现在D-大学、A-D和家-A上。

1. 最后一句口语内容在“当你写出来时，它是”之后被截断了。

1. 公式

   $$\text{university} \leftarrow D$$
   解释

   从终点出发，沿着其前驱箭头反向回到 D。

   步骤依据

   音频提示与边 D-大学 的黄色高亮显示。

   视频直接表达
2. 公式

   $$D \leftarrow A$$
   解释

   沿着 D 的前驱箭头反向回到 A。

   步骤依据

   音频提示与边 A-D 的黄色高亮显示。

   视频直接表达
3. 公式

   $$A \leftarrow \text{home}$$
   解释

   沿着 A 的前驱箭头反向回到起点。

   步骤依据

   音频提示与边 家-A 的黄色高亮显示。

   视频直接表达
4. 公式

   $$\text{home} \rightarrow A \rightarrow D \rightarrow \text{university}$$
   解释

   将逆向链路反转，以正向顺序陈述该路径。

   步骤依据

   由观察到的前驱序列推导得出。

   依据视频推导

前驱指针标识出最短路径为：家 → $A \to D$ → 大学。

1. 声音
   观察依据

   讲解者叙述了反向追踪路径并累加距离的过程。

2. 图示
   观察依据

   视觉上高亮显示该路径，并写出序列“家 → $A \to D$ → 大学（7）”。

1. 公式

   $$$$
   解释

   从终点节点“大学”开始。

   步骤依据

   目标是找到通往“大学”的路径。

   视频直接表达
2. 公式

   $$$$
   解释

   沿着高亮的黄色边反向追踪，找到前驱节点“D”。

   步骤依据

   通过观察图可知，边 D → 大学 属于最短路径树的一部分。

   视频直接表达
3. 公式

   $$$$
   解释

   继续从“D”反向追踪至其前驱节点“A”。

   步骤依据

   观察图可知，边 $A \to D$ 属于最短路径树的一部分。

   视频直接表达
4. 公式

   $$$$
   解释

   从“A”反向追踪至起始节点“家”。

   步骤依据

   目视检查可知，边 home → A 属于最短路径树。

   视频直接表达
5. 公式

   $$$$
   解释

   写出完整的路径序列：home → $A \to D$ → university。

   步骤依据

   将追踪出的各步合并，即可得到完整的最短路径。

   视频直接表达
6. 公式

   $$2 + 2 + 3 = 7$$
   解释

   通过累加路径上各条边的权重来计算总距离（home→A 为2，$A\to D$ 为2，D→university 为3）。

   步骤依据

   带权图中路径长度的定义。

   依据视频推导

最短路径为 home → $A \to D$ → university，其最小距离为7。

1. 图示
   观察依据

   一个带权图，其顶点包括家、大学、A、B、C、D、E。

2. 声音
   观察依据

   本例中，我们要找从家到大学的最短路径。

求从‘家’顶点到‘大学’顶点在给定带权网络中的最短路径。

1. 带权无向图，顶点包括：家、大学、A、B、C、D、E。

2. 边的权重：家-A=2，家-C=3，$A-B=4$，$A-C=2$，$A-D=2$，$B-D=2$，B-大学=2，$C-E=1$，D-大学=3，E-大学=5。

确定最短路径所经过的顶点序列及其总权重。

1. 公式

   $$Initialize: circle 'home', set d(home)=0.$$
   解释

   从源顶点开始执行该算法。

   步骤依据

   戴克斯特拉（Dijkstra）算法的基础情形。

   视频直接表达
2. 公式

   $$Update neighbors of 'home': d(A)=2, d(C)=3.$$
   解释

   计算从源顶点出发的初始距离。

   步骤依据

   将各边权重加到 d(家) 上。

   视频直接表达
3. 公式

   $$Select min uncircled: circle 'A' (d=2), draw arrow from 'home'.$$
   解释

   选择距离最近的未访问顶点。

   步骤依据

   对应的式子为：$2 < 3$。

   视频直接表达
4. 公式

   $$Update neighbors of 'A': d(B)=6, d(D)=4, d(C)=min(3, 4)=3.$$
   解释

   通过‘A’重新计算各顶点的距离。

   步骤依据

   $2+4=6$，$2+2=4$，$2+2=4$。对顶点 C 保留最小值。

   视频直接表达
5. 公式

   $$Select min uncircled: circle 'C' (d=3), draw arrow from 'home'.$$
   解释

   选择下一个距离最近的未访问顶点。

   步骤依据

   对应的式子为：$3 < 4$, 6。

   视频直接表达
6. 公式

   $$Update neighbors of 'C': d(E)=4.$$
   解释

   通过‘C’重新计算各距离。

   步骤依据

   对应的式子为：$3+1=4$。

   视频直接表达
7. 公式

   $$Select min uncircled: circle 'D' (d=4), draw arrow from 'A'.$$
   解释

   选择下一个距离最近的未访问顶点；D与E距离相同，任选其一打破平局。

   步骤依据

   对应的式子为：4 <= 4, 6。

   视频直接表达

视频片段结束时算法仍在运行；截至目前找到的最短路径通向D，距离为4。

对加圈顶点及箭头的视觉追踪，验证了路径的构建过程。

1. 图示
   观察依据

   逐步分析一个带权图，其顶点包括家、A、B、C、D、E、大学。

2. 声音
   观察依据

   讲解者叙述了标签更新、划去操作、选择未加圈的最小顶点，以及最终路径的重构过程。

1. 开头几句话不完整，最后一句在“当你写出来时，它是”之后被截断。

利用所演示的戴克斯特拉算法，在图中所示的带权图上，求出从家到大学的最短距离及对应路线。

1. 初始可见的已确定标签：家 = 0，$A = 2$，$C = 3$，$D = 4$。

2. 可见的边权包括：家-A = 2，家-C = 3，$C-A = 2$，$C-E = 1$，$A-B = 4$，$A-D = 2$，A-大学 = 3，$B-D = 2$，B-大学 = 2，D-大学 = 3，E-大学 = 5。

3. E 的初始未加圈标签为 4。

4. 大学在本片段后续更新前的候选标签为 7。

求出从家到大学的最终最短距离；并求出对应的最短路径。

1. 公式

   $$d(B)=2+4=6$$
   解释

   从 A 出发，为 B 计算一个候选标签 6。

   步骤依据

   音频：“四加二是六”，同时显示相关标签与边权。

   视频直接表达
2. 公式

   $$d(\text{university})=7$$
   解释

   通过 D 的路径已在大学处预先置入一个候选标签 7。

   步骤依据

   可见标签7，音频为“四加三等于七”；该算术运算对应的是D→大学，而非A→大学。

   视频直接表达
3. 公式

   $$\text{select }E\text{ because }4<7$$
   解释

   尚未到达大学节点，请选择最小的未标记顶点E，其标签为4。

   步骤依据

   音频明确指出最小的未标记顶点是“下方这个四”。

   视频直接表达
4. 公式

   $$d(\text{university})=4+5=9$$
   解释

   从E出发，计算大学节点的一个候选值9。

   步骤依据

   音频：“到大学的距离是九”，图中E与大学之间的边权重为5。

   视频直接表达
5. 公式

   $$\text{keep }7\text{, discard }9$$
   解释

   将9与现有的7比较，并划去9。

   步骤依据

   音频：“我们将划去九，因为它不是最小的。”

   视频直接表达
6. 公式

   $$\text{select }B\text{ with }6$$
   解释

   接下来选择最小的未标记顶点B，其标签为6。

   步骤依据

   音频指出B是下一个最小的未标记顶点，图中将6圈出。

   视频直接表达
7. 公式

   $$d(\text{university})=6+2=8$$
   解释

   从B出发，计算大学节点的一个候选值8。

   步骤依据

   音频：“六加二等于八”，图中B与大学之间的边权重为2。

   视频直接表达
8. 公式

   $$\text{keep }7\text{, discard }8$$
   解释

   将8与7比较，并划去8。

   步骤依据

   音频：“划掉八，因为八比七大。”

   视频直接表达
9. 公式

   $$d(\text{university})=7\text{ final}$$
   解释

   在大学处圈出7，作为最终的最短距离。

   步骤依据

   音频：“这告诉我们，从家到大学的最短距离是七。”

   视频直接表达
10. 公式

    $$\text{path}=\text{home}\rightarrow A\rightarrow D\rightarrow \text{university}$$
    解释

    沿着前驱箭头从大学反向回溯，以还原路径。

    步骤依据

    音频及黄色反向高亮：从大学→$D\to A$→家。

    视频直接表达

最短距离 = 7；最短路径 = 家 → $A \to D$ → 大学。

答案在片段中通过以下方式得到验证：将大学处所有后续候选标签（来自E的9和来自B的8）与7比较，并沿记录的前驱箭头从大学反向追踪至家。

1. 图示
   观察依据

   一个带权图，其节点包括 home、A、B、C、D、E、university。

2. 声音
   观察依据

   讲解者说明如何求从 home 到 university 的最短路径。

给定一个表示地点及通行时间的带权图，求从 'home' 到 'university' 的最短路径及其总距离。

1. 一个图，其顶点为 home、A、B、C、D、E、university。

2. 边的权重表示距离或时间。

3. 预先计算出到各节点的最短距离（以蓝色圆圈标示）。

找出构成最短路径的节点序列，并计算其总权重。

1. 公式

   $$$$
   解释

   观察图中高亮显示的黄色路径。

   步骤依据

   该视觉辅助提示表明了最优路线。

   视频直接表达
2. 公式

   $$$$
   解释

   从‘大学’反向追踪至‘家’：大学 <- $D <- A$ <- 家。

   步骤依据

   沿着最短路径树中的有向边进行追踪。

   视频直接表达
3. 公式

   $$$$
   解释

   写出正向路径：家 - A - D - 大学。

   步骤依据

   将反向追踪结果反转，得到符合逻辑的顺序。

   视频直接表达
4. 公式

   $$2 + 2 + 3 = 7$$
   解释

   累加各条边的权重：(家, A)=2，(A, D)=2，(D, 大学)=3。

   步骤依据

   计算整条路径的总代价。

   依据视频推导

路径：家 - A - D - 大学；最小距离：7。

各边权重之和与说话者所写的最终距离值一致。

1. 图示
   观察依据

   含7个顶点和10条边的静态带权图。

1. 顶点：家、大学、A、B、C、D、E

2. 带数值权重的边

1. 蓝色标注（数字、圆圈、箭头、划掉标记）随时间依次添加。

1. 底层图结构及边权重保持不变。

视觉变化表示在固定网络上逐步执行戴克斯特拉算法的过程。

1. 图示
   观察依据

   该图显示：家处标有圈出的0，A处标有圈出的2，C处标有圈出的3，D处标有圈出的4；E处标有未圈出的4；大学处标有未圈出的7；B处标有未圈出的6。

1. 带权图

2. 顶点：家、A、B、C、D、E、大学

3. 圈出的标签：0、2、3、4

4. 未加圆圈的标签6、4、7

5. 蓝色前驱箭头

1. 候选标签6在B处、7在大学处，可见于与A和D相关的更新中。

1. 边的权重保持不变。

2. 已加圆圈的标签0、2、3和4不发生变化。

该片段从中途开始播放，此时已有若干顶点被确定，且候选标签已传播至B和大学。

1. 图示
   观察依据

   E处未加圆圈的4被用蓝色加圆圈。

2. 动画
   观察依据

   从C到E画出一条蓝色箭头。

1. 顶点E

2. E处的标签4

3. 顶点C

4. 边 C-E

1. E 从无圈状态变为有圈状态。

2. 添加一条前驱箭头 $C\to E$。

1. E 处的标签值4保持不变。

2. 其他已确定的标签保持不变。

因为 E 处的4是最小的无圈标签，所以 E 在目标标签7被接受之前即被确定。

1. 图示
   观察依据

   一个红色矩形框包围了 E、边 E-大学 和 大学。

1. 顶点 E

2. 边 E-大学

3. 顶点 大学

4. 红色矩形

1. 涉及E和university的区域以红色高亮显示。

1. 红色框本身不会改变任何数值标签。

2. 边权重保持为5。

该高亮支持口头反事实解释：从E到university的一条更小的边本可击败当前目标标签7。

1. 图示
   观察依据

   一个 9 在大学里写在现有的 7 下方。

2. 图示
   观察依据

   该9随后被划掉。

1. 顶点university

2. 标签7和9

3. 边E-university

1. 一个新的候选标签9出现在university处。

2. 9被划掉，而7保留不变。

1. 原有标签7保持可见。

2. 边权E-university仍为5。

由E更新得到4＋5＝9，比当前最优值7更差，因此被舍弃。

1. 图示
   观察依据

   顶点B处的标签6被加圈。

2. 动画
   观察依据

   画出一条从A指向B的蓝色箭头。

1. 顶点B

2. 顶点B处的标签6

3. 顶点A

4. 边A-B

1. B由未加圈变为加圈。

2. 添加一条前驱箭头$A\to B$。

1. 6在B处的值保持不变。

2. 先前已确定的标签保持固定。

E处理完毕后，B拥有剩余未加圈标签中最小的一个，因此接下来被确定。

1. 图示
   观察依据

   在大学处写下8，紧邻已有的7。

2. 图示
   观察依据

   8被划掉。

1. 顶点大学

2. 标签7和8

3. 边B-大学

1. 大学处出现一个新的候选标签8。

2. 8被划掉，而7保留。

1. 标签7仍为最佳候选。

2. B大学处的边权重保持为2。

来自B的更新得到6＋2＝8，该值大于7，因此目标标签未被改进。

1. 图示
   观察依据

   大学处的标签7以蓝色圆圈标出。

1. 顶点：大学

2. 标签7

1. 大学处未加圆圈的7变为加圆圈。

1. 没有新的候选者取代7。

2. 所有更小的未加圆圈顶点都已被处理完毕。

目标标签7现被确认为从家到大学的最短距离。

1. 动画
   观察依据

   黄色高亮依次出现在D大学、A-D、家-A上。

2. 声音
   观察依据

   讲述者口述从大学经D、A回到家的逆向路径。

1. 边 D-大学、A-D、家-A

2. 顶点 大学、D、A、家

3. 黄色高亮

1. 边按从终点指向起点的逆序依次高亮。

1. 高亮过程中，底层图结构与标签均保持不变。

2. 被高亮的边对应于所记录的前驱箭头。

动画通过反向追踪前驱指针，直观地重构最短路径，得到 家 → $A \to D$ → 大学。

1. 图示
   观察依据

   边 home→A、$A\to D$ 和 D→university 以粗黄色高亮显示。

1. 图的边

1. 特定的边被涂成黄色，以区别于图中其余部分。

1. 底层图结构保持不变。

黄色高亮在视觉上表示算法所找到的构成最短路径的一系列边。

1. 动画
   观察依据

   手写文字依次出现在屏幕底部：'university'，然后是'- D - university'，接着是'- A - D - university'，再是'home - A - D - university'，最后是'(7)'。

1. 文字标签

1. 文字逐步添加，以构建最终的路径字符串。

1. 上方的图示保持静止。

该动画演示了通过从终点反向追踪来重构路径的过程，并最终以正确的正向顺序写出路径，同时给出总距离。

1. 声音
   观察依据

   当某个顶点处出现两个或更多数字时，我们将划掉所有不等于最小值的数字。

学生可能在单个顶点处保留多个距离值，从而导致后续步骤中产生混淆。

仅应保留最小的距离值；所有更大的值必须明确划掉。

1. 声音
   观察依据

   现在，我们不能仅因已得到七就断定它是最短距离，因为我们仍需考虑其他顶点。

2. 声音
   观察依据

   我们无法立刻圈出那个七的根本原因在于：若从 E 到大学的边权仅为一或二，则实际会给出一条更短的路径。

一旦终点处出现某个数字，人们可能误以为它已是最终最短距离而立即停止。

该片段明确显示，大学处的7并未立即被圈出，因为还有一个标号为4、未被圈出的更小顶点E仍需处理；只有在所有更小的候选点都被处理完毕后，目标标号才能最终确定。

1. 声音
   观察依据

   假设从E到大学的边权为1或2的讨论。

2. 图示
   观察依据

   后续候选值9和8被写在大学处，并与7进行比较。

人们可能误以为，只要存在一条通往目的地的路径，即可直接确定答案，而无需检验其他尚未确定的分支。

该例题检验了经由E和B的替代路径，分别得到9和8，但因二者均大于7而予以舍弃。

1. 声音
   观察依据

   先顺序讲解初始化，再讲解更新邻居。

必须完成初始化步骤后，才能开始更新邻居。

1. 声音
   观察依据

   先顺序讲解更新邻居，再讲解选取最小值。

必须先用新距离更新邻居，算法才能选取下一个访问顶点。

1. 声音
   观察依据

   在计算出多个到 C 的距离后，立即划掉较大数字的解释。

当多条路径到达同一顶点时，划去较大数字的规则是邻接点更新步骤的直接结果。

1. 声音
   观察依据

   讲解者首先坚持必须先处理最小的未圈出顶点，之后才在大学处圈出7。

2. 图示
   观察依据

   E和B在大学之前即已被确定。

最终距离7依赖于这样一条规则：必须先处理最小的未圈出顶点，目标点方可被宣告完成。

1. 图示
   观察依据

   前驱箭头是在算法运行过程中绘制的。

2. 声音
   观察依据

   最终路径通过“逆向追踪箭头”获得。

路径重构依赖于此前记录的前驱箭头；若无这些箭头，便无法还原逆向路径。

1. 图示
   观察依据

   所有算法操作都依赖于比较顶点上的数字标签。

2. 声音
   观察依据

   讲解者反复将这些标签称为距离。

选择下一个顶点的规则，预设了听众理解：每个数字标签代表从源点出发的当前距离估计值。

1. 图示
   观察依据

   整段视频仅展示了一个完整的图示例题。

2. 声音
   观察依据

   旁白具体应用了选择规则与更新规则。

该例题体现了通用方法：选取未加圆圈的最小标签顶点，并更新其邻接顶点的候选距离。

1. 声音
   观察依据

   假设从 E 到大学的边权为1或2，用于解释为何7不能立即加圆圈。

经由 E 的更短路径这一假设，与“首个目标标签可立即采纳”的错误观念形成对比。

1. 声音
   观察依据

   说话人从描述路径转为陈述最短距离。

一旦通过回溯确定了路径，最短距离即为该路径上所有边的权重之和。

1. 声音
   观察依据

   在起始顶点处写上零的解释。

1. 初始化步骤

1. 声音
   观察依据

   圈出最小未圈数字的解释。

1. 选择下一个顶点

1. 声音
   观察依据

   一个顶点上有两个或更多数字时的处理规则。

1. 处理多个距离

1. 声音
   观察依据

   “我们并不能直接断定七就是最短距离”

2. 声音
   观察依据

   “倘若从 E 到大学的那条边权仅为一或二”

1. 在结束前，先选出最小的未加圆圈顶点
2. 错误地将首个目标标签视为最终结果

1. 图示
   观察依据

   数字始终附着于顶点之上，并持续进行比较。

2. 声音
   观察依据

   从家到B的距离是六

1. 本例题中数值顶点标签的含义

1. 声音
   观察依据

   即到大学的距离是九

2. 声音
   观察依据

   六加二是八

1. 本例题中数值顶点标签的含义
2. 在结束前，先选出最小的未加圆圈顶点

1. 声音
   观察依据

   从家到大学的最短距离是七

1. 从家到大学的最短距离

1. 声音
   观察依据

   从大学出发反向追溯，我们经过了D……A……家。

2. 动画
   观察依据

   黄色高亮显示了反向追踪的路径。

1. 通过沿前驱箭头反向追踪来重构最短路径
2. 前驱箭头记录了生成该标签的路径。

1. 声音
   观察依据

   最小的未画圈顶点是下方这个四

2. 图示
   观察依据

   E在大学被最终确定之前就已被画圈。

1. 在结束前，先选出最小的未加圆圈顶点
2. 错误地将首个目标标签视为最终结果

1. 声音
   观察依据

   从右向左推导路径的说明。

1. 最短路径算法中的路径回溯

1. 声音
   观察依据

   关于标出最短距离的陈述。

1. 报告最短距离