我试图提出一种使用BFS为无向加权图寻找单源最短路径算法的解决方案。
我想出了一个解决方案，将每个x的边缘权重转换为顶点之间的每个权重为1的顶点之间的x边缘，然后运行BFS。我会得到一个新的BFS树，由于它是一棵树，所以从根节点到其他每个顶点只有1条路径。
我遇到的问题是试图对以下算法进行分析。每个边缘需要访问一次，然后根据其权重划分为相应数量的边缘。然后我们需要找到新图的BFS。
访问每个边缘的成本为O（m），其中m是边缘的数量，因为每个边缘都要被分割一次。假设新图具有km边（例如m'）。BFS的时间复杂度为O（n + m'）= O（n + km）= O（n + m），即时间复杂度保持不变。给定的证明正确吗？
[我知道我可以在这里使用Dijkstra的算法，但是我对分析这种基于BFS的算法特别感兴趣。
您在此处包括的分析接近但不正确。如果假设每个边的成本最多为k，则新图将具有O（kn）个节点（每个边添加了额外的节点）和O（km）个边，因此运行时间将为O（kn + km） 。但是，您不能在此假设k为常数。毕竟，如果我增加了边缘的权重，则确实会增加代码运行所花费的时间。因此，总的来说，您可以给出O（kn + km）的运行时间。
注意，这里的k是运行时的一个独立参数，与m和n相同。这很有意义-较大的权重可为您提供更大的运行时间。
（（请注意，这不是多项式时间算法。而是pseudopolynomial-time algorithm，因为写出权重k所需的位数为O（log k）。]