标签: bellman-ford

所以我是Java新手,我做了一些c编程.我正在尝试建立一个虚拟的节点网络,每个节点都需要成为一个线程.仅允许节点与其邻居节点通信.将有一个主节点可以与任何节点通信,但节点必须相互通信才能返回主节点.主节点邻居可以与主节点通信.

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

我的问题是如何在Java中的线程之间传递信息.我需要能够让主节点给出所有常规节点的位置信息.我需要常规节点才能将消息传递给它们的邻居常规节点.

这是我的git回购,如果你想看看我现在的代码.

https://github.com/fieldju/cs372_project

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

对于任何看过这个并希望看到结果的人来说,这只是一个更新.我已经启动并运行节点并进行通信,您可以查看代码

https://github.com/fieldju/cs372_project

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

我使用矩阵d来呈现图形。d.(i).(j)装置之间的距离i和j; v表示图中的节点数。

此图中可能存在负循环。

我想检查是否存在负循环。我从Floyd-Warshall的变体中写了以下内容：

let dr = Matrix.copy d in

(* part 1 *)
for i = 0 to v - 1 do
  dr.(i).(i) <- 0
done;

(* part 2 *)
try
  for k = 0 to v - 1 do
    for i = 0 to v - 1 do
      for j = 0 to v - 1 do
          let improvement = dr.(i).(k) + dr.(k).(j) in  
          if improvement < …

我有一个关于贝尔曼福特算法的问题。我创建了这个程序，当给定一个图时，它将输出源节点和所有其他节点之间的最短距离。该部分工作得非常好，所以我有这样的输出：

The cost table is: 
Destination:   0    1   2   
Cost:          0    4   6

例如，我的源和节点 2 之间的最短距离是 6，这很好。但现在我想得到实际的路线，而不仅仅是它们的成本。就像从 s 到 v 的路线成本不是只有 5 一样，我想要类似路线 s-> b -> v 的路线。使用 Bellman Ford 是否可以实现这一点，还是我遗漏了其中的某些部分？

非常感谢。

我正在研究 这个链接http://algs4.cs.princeton.edu/44sp/BellmanFordSP.java上的来自书籍的算法源代码的单源最短路径的queue-based方法.Bellman-Ford algorithmRobert Sedgewick and Kevin Wayne - Algorithms, 4th edition

我有两点是一个疑问,另一个是代码改进建议.

1. 在上述方法中,以下是用于放松到顶点的距离的松弛方法的代码.

   for (DirectedEdge e : G.adj(v)) {
       int w = e.to();
       if (distTo[w] > distTo[v] + e.weight()) {
           distTo[w] = distTo[v] + e.weight();
           edgeTo[w] = e;
           if (!onQueue[w]) {
               queue.enqueue(w);
               onQueue[w] = true;
           }
       }
       if (cost++ % G.V() == 0){
           findNegativeCycle();
       }
   }
   

   Run Code Online (Sandbox Code Playgroud)

在该方法中,在找到负循环之前使用以下条件.

if (cost++ % G.V() == 0){
     findNegativeCycle();
}

以上他们将成本除以vertices图表中的数量来检查negative cycle.这可能是因为放松是在V-1时间上进行的,并且如果放松Vth …

我正在尝试改进贝尔曼-福特算法的性能，我想知道改进是否正确。

我运行松弛部分不是 V-1 而是 V 次，并且涉及一个布尔变量，true如果在外循环迭代期间发生任何松弛，则设置该变量。如果 n 处没有发生放松。当 n <= V 时，它从最短路径的循环中返回，但如果它在 n = V 迭代时放松，则意味着我们有一个负循环。

我认为这可能会提高运行时间，因为有时我们不必迭代 V-1 次来找到最短路径，而且我们可以更早返回，而且它也比用另一个代码块检查循环更优雅。

AdjacencyListALD graph;

int[] distTo;
int[] edgeTo;

public BellmanFord(AdjacencyListALD g)
{
    graph = g;
}

public int findSP(int source, int dest)
{

    // initialization

    distTo = new int[graph.SIZE];
    edgeTo = new int[graph.SIZE];

            for (int i = 0;i<graph.SIZE;i++)
            {
                distTo[i] = Integer.MAX_VALUE;
            }

            distTo[source] = 0;

    // relaxing V-1 times + 1 for checking negative cycle = V times

    for(int i …

图像：4 次迭代，其中 (a) 是原始图。(b), (c), (d), (e) 对应于每次迭代后的结果。“算法介绍 3rd”中的示例

嗨，我对算法的几个方面不太了解。我希望有人可以提供帮助。以下是我的问题。

就我而言，在每次迭代中，所有边都是松弛的。我希望所有节点都在第一次迭代中更新距离。那么为什么在第一次迭代 (b) 中，只更新了节点 t 和 y 的距离，而另一个仍然是无穷大？

另一个问题是，为什么需要（节点号 - 1）所有边都松弛的迭代？保证在每次迭代中实现什么，以便算法必须在（节点数 - 1）时间内运行以确保找到最短路径，只要不存在负权重循环？

我已成功实施Bellman-Ford,以便在边缘具有负重量/距离时找到最短路径的距离.我无法让它返回所有最短路径(当有最短路径时).我设法用Dijkstra获得所有最短的路径(在给定的节点对之间).Bellman-Ford有可能吗？(只是想知道我是否在浪费时间尝试)

我想在大量图上对 bellman Ford 算法进行执行时间分析，为此我需要生成大量随机 DAGS，并且可能具有负边权重。

我在 python 中使用 networkx。networkx 库中有很多随机图生成器，但是将返回带有边权重和源顶点的有向图的将是什么。

我正在使用 networkx.generators.directed.gnc_graph() 但这并不能完全保证只返回一个源顶点。

有没有办法在有甚至没有networkx的情况下做到这一点？

像Bellman-Ford算法和Dijkstra算法这样的算法用于找到从图上的单个起始顶点到每个其他顶点的最短路径.但是,在我写的程序中,起始顶点的变化比目标顶点的变化频繁得多.有什么算法可以反过来 - 也就是说,给定一个目标顶点,从每个起始顶点找到最短路径？

我刚刚开始学习新算法，但是当我在极客上阅读极客的Bellman Ford算法时，就陷入了困境：-http: //www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/

那里写着-

该算法以自下而上的方式计算最短路径。它首先为路径中最多具有一个边缘的最短路径计算最短距离。然后，它计算最多具有2条边的最短路径，依此类推。

在外循环的第i次迭代之后，将计算最多i个边的最短路径。可以有最大| V |。–在任何简单路径中都有1条边，这就是为什么外循环运行| v |的原因 – 1次。这个想法是，假设不存在负权重循环，如果我们计算出最多具有i个边缘的最短路径，那么对所有边缘进行的迭代将确保给出最多具有（i + 1）个边缘的最短路径。

让我们通过下面的示例图了解算法。图像是从此来源获取的。

假设给定的源顶点为0。将所有距离初始化为无限，除了到源本身的距离。图中的顶点总数为5，因此所有边必须处理4次。

在下面的示例中，如果边的顺序为-（AB），（BE），（ED），（DC），（AC），（BC），（DB），（BD），则仅一次迭代将计算最短甚至具有2-3条边的路径，这与“首先为路径中最多具有一条边缘的最短路径计算最短距离。然后，它计算出具有最多2条边缘的最短路径，以此类推”相反在外循环的第ith次迭代之后，计算出最多具有i条边的最短路径“因此，在更改边的顺序时，该语句将被证明是错误的。

让我们通过下面的示例图了解算法。图像是从此来源获取的。

假设给定的源顶点为0。将所有距离初始化为无限，除了到源本身的距离。图中的顶点总数为5，因此所有边必须处理4次。

让所有边缘按以下顺序处理：（B，E），（D，B），（B，D），（A，B），（A，C），（D，C），（B，C） ，（E，D）。第一次处理所有边缘时，我们得到以下距离。第一行显示初始距离。第二行显示处理边缘（B，E），（D，B），（B，D）和（A，B）时的距离。第三行显示处理（A，C）时的距离。第四行显示何时处理（D，C），（B，C）和（E，D）。

第一次迭代保证给出最长为1个边长的所有最短路径。第二次处理所有边缘时，我们得到以下距离（最后一行显示最终值）。

第二次迭代保证给出最长为2个边长的所有最短路径。该算法将所有边缘再处理2次。在第二次迭代后将距离最小化，因此第三次和第四次迭代不会更新距离。