使用Dijkstra的方法在加权有向图中找到权重最低的循环
嗨，我在纠结这个问题。其内容如下：
- 首先，我们如何知道图中有多少个循环，以及如何检查这些循环？
- 还有，为什么是evlogv？根据我的理解，你应该遍历所有的顶点，因此使它成为vlogv。
这是我个人的学习，所以如果任何人有一个例子，他们可以使用，它将大大帮助我！我并不是真的在寻找伪代码--只是一个通用算法来理解如何使用从一个节点到所有节点的最短路径来帮助我们解决这个问题。谢谢你！
共有1个答案
从每个顶点调用Dijkstra的算法，寻找到自身的最短路径，如果存在的话。从任一顶点到自身的最短路径就是最小循环。Dijkstra算法需要O（E log V）,因此总时间为O（VE log V）。
注意，这个时间可能比Floyd-Warshall更差，因为图中可能有O(v^2)条边。
-
给我一个图中名为“a”的顶点，对于v中的每一个v，我需要找到从a到v的路径的权重，它在时间O(v+E)中权重最低。我不得不只使用BFS或DFS（尽管这很可能是BFS的问题）。 我想过要制作一个新的图，其中边为0的顶点是统一的，然后在它上面运行BFS，但是这会破坏图的方向（如果图是无向的或者权重是{2,1}，对于边为2，我会创建一个新的顶点）。 如果有任何帮助，我将不胜感激。 谢谢
-
这是我的算法。 我做了一个。每次当我找到时，我都知道我得到了一个有向循环。 然后我将暂时沿着向后（直到我在循环中遍历所有顶点），并计算。 我的算法正确吗？ 如果我的算法正确，时间复杂度是多少？ 这个问题有没有更好的算法？
-
在一个加权有向图中，我需要找到两个结点s，t之间的最短路径。以下是限制： 权重可以为负值。 路径必须经过一个特定的边，让我们从节点u到V调用her e和shes。 输出路径必须简单，即我们只通过一个节点一次。 因为我希望它最短，所以我将检查在从s到u之前从v到t运行bellman ford是否比相反的方式更快（如果有节点，两个节点都使用where是放置它的最佳位置）。 谢谢你的帮助！
-
我正在学习最小生成树。我研究了Prim的加权有向图算法。 算法简单 您有两组顶点：已访问和未访问 将所有边的距离设置为无穷远 从未访问集合中的任意顶点开始并探索其边 在所有边中，如果目标顶点没有被访问，并且如果边的权重小于目标顶点的距离，则用该边的权重更新目标顶点的距离 选择距离最小的未访问顶点，然后再进行一次，直到所有顶点都访问完 相信通过以上算法，能够在所有的生成树中找到代价最小的生成树，即最
-
假设我们有一个有向图，它同时包含正加权边和负加权边。 我知道最短路径解决方案是Bellman-Ford算法。 我的问题是：为什么我们不能只是在所有的边成本上增加一些大的值N，这样就不再有负边了，然后使用效率高得多的Dijkstra算法？
-
我有一个有向图，边上的权值是非负的。 我的算法应该做到以下几点： 获取从顶点u到顶点V的所有路径 计算从u到v的每条路径上的最小加权边 计算我从上面计算的最小加权边的最大值。