使用 BFS 的无向加权图的单源最短路径
Single source shortest path using BFS for a undirected weighted graph
我试图想出一个使用 BFS 为无向加权图寻找单源最短路径算法的解决方案。
我想出了一个解决方案，将每条边的权重（比如 x）转换为顶点之间的 x 条边，每条新边的权重为 1，然后 运行 BFS。我会得到一棵新的 BFS 树，因为它是一棵树，所以从根节点到每个其他顶点只存在一条路径。
我遇到的问题是试图对以下算法进行分析。每条边都需要访问一次，然后根据其权重拆分为相应数量的边。然后我们需要找到新图的BFS。
访问每条边的成本是 O(m)，其中 m 是边的数量，因为每条边都被访问一次以将其拆分。假设新图有 km 条边（比如 m'）。
BFS 的时间复杂度为 O (n + m') = O(n + km) = O(n + m) 即时间复杂度保持不变。
给出的证明是否正确？
我知道我可以在这里使用 Dijkstra 算法，但我对分析这种基于 BFS 的算法特别感兴趣。
您在此处包含的分析很接近但不正确。如果您假设每条边的成本最多为 k，那么您的新图将具有 O(kn) 个节点（每条边添加了额外的节点）和 O(km) 个边，因此 运行 时间将为 O （千米+千米）。但是，您不能假设 k 在这里是常数。毕竟，如果我增加边缘的权重，我确实会增加你的代码所花费的时间 运行。所以总的来说，你可以给出 O(kn + km) 的 运行 时间。
注意这里的k是运行时间的单独参数，m和n也是一样。这是有道理的 - 更大的权重给你更大的运行倍。
（请注意，这不被视为多项式时间算法。相反，它是一个 pseudopolynomial-time algorithm，因为写出权重 k 所需的位数是 O(log k)。）
我试图想出一个使用 BFS 为无向加权图寻找单源最短路径算法的解决方案。
我想出了一个解决方案，将每条边的权重（比如 x）转换为顶点之间的 x 条边，每条新边的权重为 1，然后 运行 BFS。我会得到一棵新的 BFS 树，因为它是一棵树，所以从根节点到每个其他顶点只存在一条路径。
我遇到的问题是试图对以下算法进行分析。每条边都需要访问一次，然后根据其权重拆分为相应数量的边。然后我们需要找到新图的BFS。
访问每条边的成本是 O(m)，其中 m 是边的数量，因为每条边都被访问一次以将其拆分。假设新图有 km 条边（比如 m'）。 BFS 的时间复杂度为 O (n + m') = O(n + km) = O(n + m) 即时间复杂度保持不变。 给出的证明是否正确？
我知道我可以在这里使用 Dijkstra 算法，但我对分析这种基于 BFS 的算法特别感兴趣。
您在此处包含的分析很接近但不正确。如果您假设每条边的成本最多为 k，那么您的新图将具有 O(kn) 个节点（每条边添加了额外的节点）和 O(km) 个边，因此 运行 时间将为 O （千米+千米）。但是，您不能假设 k 在这里是常数。毕竟，如果我增加边缘的权重，我确实会增加你的代码所花费的时间 运行。所以总的来说，你可以给出 O(kn + km) 的 运行 时间。
注意这里的k是运行时间的单独参数，m和n也是一样。这是有道理的 - 更大的权重给你更大的运行倍。
（请注意，这不被视为多项式时间算法。相反，它是一个 pseudopolynomial-time algorithm，因为写出权重 k 所需的位数是 O(log k)。）