找到给定函数的最小权重的路径

Question

我给出了一个无向图G = (V, E)，顶点s的V和函数w:E->{0,1}。给定任何v在V，我需要返回一个路径的权重（路径的权重=路径的边的权重的总和）与最小权重从s到v在O(|V| + |E|)时间。
。
这听起来像是一个我懒得解决的家庭作业问题（我时常得到这些答案），但我一直在努力解决这个问题，我非常感谢您的帮助或指导可能对我有用。

Answer 1

这个问题可以通过模拟BFS算法来解决，但是用deque（D）而不是队列。 Algo使用标记列表“为每个顶点标记”，初始化为false。 s的距离将出现，因此您可以存储它们或使用“实时”。 D将存储对（顶点，distance_label）。

Algo开始：

D由（s，0）初始化。

在每次迭代中，从距离标签d的D（顶点v）中提取前（头）顶点。

如果v已经标记为已到达，则跳至下一次迭代。

否则，将v标记为已达到。现在，d是s和v之间的正确距离，对于每个未到达的邻居（顶点w），更新它的距离标签（d_w = d + dist（v，w）），并将pair（w，d_w） （v，w）= 0或放到尾部，否则。

Algo结束。

当您将它们标记为已到达时，您可以存储到所有顶点的距离。可能所有未达到的顶点都有无穷远的距离。

工作时间为O（| V | + | E |），因为您将每个顶点和每个边（在连接的组件中都用s）精确地处理一次。

算法的正确性可以通过距离s的归纳证明。