algorithm - 理解 Dijkstra 算法

Question

我正在使用此引用资料:http://www.cs.arizona.edu/classes/cs545/fall09/ShortestPath.prn.pdf

在第 3 页的最后一张幻灯片中，它说我们正在放松从 B 离开的边缘。但是在那个时候，B 和 E 之间没有边缘，尽管在那张幻灯片中考虑了 B!这怎么可能？这是作者的错误还是我遗漏了什么？

编辑

这是算法(来自那个 pdf):

这是我正在谈论的示例图:

目的是得到A和D之间的最短路径。 首先，起始顶点“A”初始化为 0 权重。然后将其余的分配给无穷大。您可以从算法的前 3 行中看出这一点。然后，接下来创建一个空的集合“S”。我们有 Q 集，它是一个队列，它将保存图中的所有顶点。我们首先从 Q 中获取最小加权顶点。在第一次，我们将在这里获取起始顶点本身，因为我们在初始化中分配了 0，其余顶点具有无穷大。因此，较小的值为 0，由此我们得到顶点 A。我们将其添加到集合“S”。然后我们将遍历这个顶点“A”的所有相邻顶点，我们将检查顶点的权重是否大于顶点“A”的权重。如果是这样，则通过将顶点“A”的权重和“A”与该相邻顶点之间的边的权重相加来重新计算相邻顶点的权重。这一直持续到集合 Q 变空。

这就是我理解的工作。

疑点在这部分:

当我们松弛从顶点“E”离开的边时，我们如何得到顶点“B”？ B和E之间没有边!!!

希望您现在对我的问题有所了解。我认为如果你看 pdf 而不是我愚蠢的解释，你会得到更多的想法。不是吗？ :P 这就是为什么我把链接也放在这个问题的开头!

Answer 1

d[v]表示:节点v之间的最短路径长度以及通过 S 中的节点的起点仅。

尽管节点 E 没有连接到 B，但我们从之前的迭代中了解到，从 A 存在一条长度为 7 的路径。至 B通过 A和 C仅有的。通过A，我们当然可以推断出存在相同的路径。 , C , 和 E仅。

请注意，在第一张幻灯片中突出显示的代码部分，它更新了 d[v]仅当存在较小的值时。如果没有，d[v]保持不变。

我注意到 OP 对 S 感到困惑.我想在此算法中添加，S只有在它可以帮助解释程序正在做什么的意义上才有用。 (我在向您解释 d[v] 的含义时使用了它。) S对程序完全没有影响。如果您删除 S，该程序的工作方式相同完全脱离程序。

此程序不为您提供最短路径。它只告诉您起始节点和图中每个节点之间的最短路径的长度。

如果要求最短路径，需要修改程序增加这个功能。以下是步骤:

• 在程序的 then 子句中，在 d[v] = d[u] + w(u,v) 之前或之后, 添加 p[v] = u .这样，您就保留了有关如何获得当前 d[v] 的信息。 ，即通过最短路径到 u然后取边u->v .
• 在整个程序完成后(即在 while 循环之后)，假设您想知道从 A 到 B 的最短路径是什么。您会发现 p[B]=C , 然后你会发现 p[C]=A .因此，路径为ACB .