基于BFS的无向加权图的单源最短路径
我试图用BFS找到无向加权图的单源最短路径算法。
我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。
我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。
访问每条边的成本是O（m），其中m是每一条边访问一次以分割它时的边数。假设新图有km边（比如m'）。BFS的时间复杂度为O（n m'）=O（n km）=O（n m），即时间复杂度保持不变。给出的证据正确吗？
我知道我可以在这里使用Dijkstra的算法，但我对分析这个基于BFS的算法特别感兴趣。
共有1个答案
您在这里包含的分析很接近，但并不正确。如果您假设每个边的成本最多为k，那么您的新图将有O（kn）节点（每个边增加了额外的节点）和O（km）边，因此运行时间将为O（kn km）。然而，您不能假设k在这里是常数。毕竟，如果我增加边缘的权重，我确实会增加代码运行的时间。所以总的来说，您可以给出O（kn km）的运行时间。
请注意，这里的k是运行时的一个单独参数，与m和n相同。这是有道理的——更大的权重会带来更大的运行时间。
（注意，这不是多项式时间算法。而是伪多项式时间算法，因为写出权重k所需的位数是O（logk）。）
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
给出了一个图G=(V，E)，它是正加权的，有向的，无圈的。我设计了一个在O(k(m+n))中运行的算法，用于报告从s到T的k-边最短路径。k-边最短路径定义为从s到t的具有k条边的路径，并且对于从s到t的所有路径，该路径的总权也必须是最小的。 由于BFS不能单独用于寻找最短路径（除非权重相等），我认为运行时间意味着使用BFS寻找具有k条边的路径。让我感到困惑的是k，因为我认为它意味着表演BFS k
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。
-
你有一辆2005年本田雅阁，油箱里还剩50英里（最大重量）。在50英里半径范围内，你可以访问哪些麦当劳的位置（图节点）？这是我的问题。 如果你有一个加权有向无环图，你如何找到在给定的权限制内可以访问的所有节点？ 我知道Dijkstra的算法，但我似乎找不到任何关于它在最小路径问题之外的用途的文档。在我的例子中，我们没有特别想结束的节点，我们只想在不超过最大权重的情况下尽可能多地结束。似乎您应该能够
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关