加权有向图中的最短路径
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制：
- 权重可以为负值。
- 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。
- 输出路径必须简单，即我们只通过一个节点一次。
因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。
谢谢你的帮助！
共有1个答案
即使找到这样的路径也是NP完全的。这是因为两个点/边不相交路径问题是有向图中的NPC问题。假设边E=(u,v）,那么你要寻找一条(s,u）,(v,t）不相交的路，但这在有向图中是NP完全的。
您可以在这里找到硬度结果:https://www.sciencedirect.com/science/article/pii/0304397580900092
您当前基于Bellman-ford的算法并不能对所有情况给出正确的答案（它可能在有路径的情况下找不到路径），然而，它可能是一个很好的启发式方法。如果您的图是无向的，那么任务就容易得多。
如果允许重复顶点，那么任何最短路径算法都是正确的方法。
-
给出了一个图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是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
我有一个有向加权图
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我试图用BFS找到无向加权图的单源最短路径算法。 我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。 我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。 访问每条边的成本是O（m），其中m是每一条边访问一
-
给出了一个边上具有任意权的有向无环图和两个特定结点s和t，其中s的内度和t的外度为0。如何确定成本为正的s到t的最短路径？