对无向加权图使用BFS的单源最短路径

Question

我试图想出一个使用BFS为无向加权图找到单源最短路径算法的解决方案。

我想出了一个解决方案，将每个边权重转换为顶点之间的x条边，每条新边的权重为1，然后运行BFS。我会得到一个新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有一条路径。

我遇到的问题是试图提出以下算法的分析。每条边都需要访问一次，然后根据它的权重被分成相应数量的边。然后我们需要找到新图的BFS。

访问每条边的成本是O(m)，其中m是边的数量，因为每条边都被访问一次以分割它。假设新图有km条边(比如m')。BFS的时间复杂度为O(n + m') = O(n + km) =O (n + m)，即保持时间复杂度不变。给出的证明正确吗？

我知道我可以在这里使用Dijkstra的算法，但我特别感兴趣的是分析这个基于BFS的算法。

Answer 1

您在此处包含的分析很接近，但并不正确。如果您假设每条边的成本最多为k，那么您的新图将有O(kn)个节点(每条边添加了额外的节点)和O(km)条边，因此运行时将为O(kn + km)。然而，你不能假设k在这里是一个常数。毕竟，如果我增加边缘上的权重，我确实会增加代码运行所需的时间。因此，总的来说，您可以给出O(kn + km)的运行时间。

请注意，这里的k是运行时的单独参数，与m和n的方式相同。这是有道理的--更大的权重会给你更大的运行时间。

(注意，这不是一个多项式时间算法。相反，它是一个对数，因为写出权重k所需的位数是O( pseudopolynomial-time algorithm k)。)