问题标签 [bellman-ford]

请建议资源来学习如何使用 Prim 算法在有向图中找到最小生成树，以及使用 Bellman-Ford 算法来计算有向图中的最短路径。

如果我们去特定的顶点，我们如何使用 Dijkstra 或 Bellman-Ford 的算法来找到图中某些边会受到影响的最短路径。这样，受影响边缘的长度将大于或小于原始长度。

我正在考虑在有向图中找到负权重循环的算法。问题是：我们有一个图 G(V,E)，我们需要找到一个有效的算法来找到一个负权重的循环。我了解此 PDF 文档中的算法

简而言之，该算法通过迭代 |V|-1 次进行松弛来应用 Bellman Ford 算法。然后它检查是否有一个可以更放松的边缘，然后存在负权重循环，我们可以通过父指针追溯它，一切顺利，我们找到一个负权重循环。

但是，我正在考虑另一种算法，即通过跟踪到目前为止您遍历的距离的总和，在图上使用深度优先搜索（DFS），我在开始时将所有节点标记为白色，并在我时将它们设为灰色搜索路径，并在完成时将它们标记为黑色，这样我知道当且仅当我找到一个访问节点并且它是灰色的（在我的路径中）时我才找到一个循环，而不是深度已经完成的黑色-第一次搜索，所以对于我的算法，如果我到达一个已经访问过的灰色节点，我检查它的更新是什么（新的距离），如果它比以前低，我知道我的权重是负的循环并可以追溯。

我的算法错了吗？如果是这样，你能找到一个反例吗？如果不是，你能帮我证明吗？

谢谢你

我目前有一个贝尔曼福特算法设置，我正在尝试打印到该节点的路径。我目前的算法是这样的：

这就是我打印出来的方式。它是递归的，但我将如何设置它以便它是迭代的？我目前收到堆栈溢出错误。

所以我是Java新手，我做了一点c编程。我正在尝试创建一个虚拟节点网络，每个节点都需要是一个线程。节点只被允许与它们的邻居节点交谈。将有一个可以与任何节点通信的主节点，但节点必须相互通信才能回到主节点。主节点邻居可以与主节点对话。

我原本打算保留一个节点的数组列表，但后来我意识到所有节点都需要有自己的线程。

我的问题是如何在 Java 的线程之间向前传递信息。我需要能够让主节点提供所有常规节点的位置信息。我需要常规节点能够将消息传递给他们的邻居常规节点。？

如果你想看看我现在开始的代码，这里是我的 git repos。

https://github.com/fieldju/cs372_project

在 CI 中制作了一个程序，该程序使用管道让孩子相互交谈，服务器连接客户端，但在这个问题中，节点要进行 p2p 通信，因为它们中的大多数不能直接与主节点/服务器通信

对于任何查看此内容并希望查看结果的人来说，这只是一个更新。我让节点启动并运行并进行通信，您可以在以下位置查看代码

https://github.com/fieldju/cs372_project

我仍在研究距离矢量的东西和其他一些事情，但到下周末，整个事情都应该完成。

我正在寻找一种算法，该算法可以找到从两个顶点说s到t的路径，如果存在路径，则该图中恰好具有k边。

如果找到多条路径，则优先选择具有单个边的最小最大权重的路径。（不是总重量）。

例如：说 K = 5

路径 1： s - a - b - c - d - t 权重为 1 - 1 - 1 - 10 - 1

路径 1 的最大权重为 10

路径 2： s - x - y - z - w - t 权重为 7 - 9 - 8 - 6 - 7

路径 2 的最大权重是 9，所以这是首选。

我该如何解决这个问题？

Please refer to the following page for Bellman ford algorithm (it shows an e.g). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm

I still don’t get it. In the first loop iteration of the outer loop, let’s say by the example, u first modify edge 1->2 and edge 1->4, what’s the problem in relaxing the edge 2->3, 2->5, 4->3, 4->5,in the same step, since we have d[2] and d[4].

我正在做一个作业问题，我需要从顶点 z 开始运行 bellman-ford 算法。它要我“在每次通过时，按照与图中相同的顺序放松边缘，并在每次通过后显示 d 和 pi 值。” 据我了解，我认为这个算法像 BFS 一样遍历图形，这从他们希望我使用的数字来看是有意义的，所以我看不出相同的路径是如何工作的。如果有人可以通过指出如何开始来为我指明正确的方向，那将非常有用。问题和问题所指的数字：

我已经实现了一个 Bellman-Ford 算法来解决一个问题（带图），但是这个解决方案太慢了，所以我用堆 (std::set) 替换了 Bellman-Ford 的队列，所以最短的解决方案路径会更快找到。（以某种方式接近 Dijkstra 算法）

现在，我在堆中插入节点编号，因此默认的 std::set 将使用节点编号而不是成本对节点进行排序。一切都很好，算法给出了正确的答案。

如果我为 std::set 引入自定义比较函数，以便节点将按它们的距离而不是按它们的数量排序，则算法不再提供到其余节点的最短距离。

这是我的比较功能：

因此，作为 BF 算法，该算法一直运行到无法改进为止。比较函数能否以某种方式“弄乱”std::set，因为这是我明白为什么添加这个比较函数会给出错误答案的唯一原因......

我的意思是，如果节点的顺序完全随机，为什么它会起作用，但如果它们按成本排序则不起作用......

在具有正边和负边​​的有向图中找到从源到目的地的最短路径，使得在路径中的任何一点，在它之前的边的总和都是负的。如果不存在这样的路径，也请报告。

我尝试使用改装的贝尔曼福特，但找不到正确的解决方案。

我想澄清几点：

1. 是的，可能会有负重循环。
2. n 是边数。
3. 如果问题有解决方案，则假设存在 O(n) 长度路径。
4. +1/-1 边缘权重。