标签: bellman-ford

经过大量的谷歌搜索后,我发现大多数消息来源称Dijkstra算法比Bellman-Ford算法"更有效".但在什么情况下Bellman-Ford算法比Dijkstra算法更好？

我知道"更好"是一个广泛的陈述,所以具体来说,我的意思是速度和空间,如果适用.当然,在某些情况下,贝尔曼 - 福特方法比Dijkstra方法更好.

我一直在研究这三个,我在下面陈述我的推论.有人能告诉我,我是否已经足够准确地理解它们了吗？谢谢.

1. Dijkstra的算法仅在您拥有单个源并且您想知道从一个节点到另一个节点的最小路径时使用,但在这种情况下失败

2. 当任何所有节点都可以作为源时,使用Floyd-Warshall的算法,因此您希望最短距离从任何源节点到达任何目标节点.只有在出现负循环时才会失败

(这是最重要的一个.我的意思是,这是我最不确定的:)

3.Bellman-Ford像Dijkstra一样使用,当时只有一个来源.这可以处理负重量,它的工作方式与Floyd-Warshall相同,除了一个来源,对吗？

如果你需要看看,相应的算法是(礼貌的维基百科):

贝尔曼 - 福特:

 procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax …

在Dijkstra的最短路径算法和其他算法中,检查边缘以查看它是否提供更好的节点路径被称为放松边缘.为什么叫做放松？

在具有正边缘和负边缘的有向图中找到从源到目的地的最短路径,使得在路径中的任何点处,在其之前的边缘的总和为负.如果不存在这样的路径也报告.

我试图使用改良的Bellman Ford,但找不到正确的解决方案.

我想澄清几点:

1. 是的,可以有负重量循环.
2. n是边数.
3. 假设问题有解,则存在O(n)长度路径.
4. + 1/-1边缘权重.

根据我的理解,当一个路由器提供另一个旧信息时,会发生计数到无穷大,这些旧信息继续通过网络向无限远传播.根据我的阅读,删除链接时肯定会发生这种情况.

因此,在此示例中,Bellman-Ford算法将针对每个路由器进行收敛,它们将具有彼此的条目.R2将知道它可以以1的成本到达R3,并且R1将知道它可以通过R2以2的成本到达R3.

如果R2和R3之间的链路断开连接,则R2将知道它不能再通过该链路到达R3并将其从表中删除.在它可以发送任何更新之前,它可能会收到来自R1的更新,它将宣传它可以以2的成本到达R3.R2可以以1的成本到达R1,因此它将更新到R3通过R1,成本为3.然后,R1将从R2接收更新,并将其成本更新为4.然后,他们将继续向无穷大提供不良信息.

我所看到的一件事提到了一些地方,除了只是一个离线的链接,比如改变一个链接的成本,还有其他可以计数到无穷大的原因.我开始考虑这个问题,从我所知道的情况来看,在我看来,链接的成本增加可能会导致问题.但是,我没有看到降低成本可能导致问题.

例如,在上面的示例中,当算法收敛并且R2具有到成本为1的到R3的路由时,并且R1具有到R2经由R2的路由,成本为2.如果R2和R3之间的成本增加到5.然后这会导致同样的问题,R2可以从R1获得更新广告,成本为2,并通过R1,R1将其成本更改为3,然后通过R2将其路由更改为4,依此类推.但是,如果成本在融合路线上降低,则不会导致变化.它是否正确？链接之间的成本增加可能导致问题,而不是降低成本？还有其他可能的原因吗？将路由器脱机与链接出去是一样的吗？

我知道Bellman-Ford算法适用于有向图.它是否适用于无向图？似乎使用无向图,它将无法检测周期,因为并行边将被视为周期.这是真的吗？算法可以应用吗？

所以我遇到了这个美丽的问题,要求你编写一个程序,找出有向图中是否存在负无穷短路径.(也可以认为是在图中存在"负循环").这是问题的链接:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499

我通过从图中的任何源开始两次运行Bellman Ford算法成功地解决了这个问题.我第二次运行算法时,检查节点是否可以放松.如果是这样,那么图中肯定存在负循环.下面是我的C++代码:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int test;
    cin>>test;

    for(int T=0; T<test; T++)
    {

        int node, E;

        cin>>node>>E; 

        int **edge= new int *[E];
        for(int i=0; i<E; i++)
        {
            edge[i]= new int [3];
            cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
        }

        int *d= new int [node];

        bool possible=false;

        for(int i=0; i<node;i++)
        {
            d[i]= 999999999;
        }

        d[node-1]=0;

        for(int i=0; i<node-1; i++)
        {

            for(int j=0; j<E; j++)
            {
                if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
                    d[edge[j][1]]=d[edge[j][0]]+edge[j][2];
            }
        }

        // time to judge!
        for(int i=0; i<node-1; i++)
        {

            for(int …

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

简而言之,该算法通过迭代| V | -1次进行松弛来应用Bellman Ford算法.之后它会检查是否有一条甚至可以放松的边缘,然后存在一个负的重量循环,我们可以通过父指针追溯它,一切顺利,我们发现负重量循环.

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

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

谢谢

我正在使用Bellman-Ford通过一些具有负权重的图表找到最短路径.该图不可能有循环,也没有双向连接.我想在图中找到K个最短路径,其中路径共享没有共同的节点.是否有算法我可以查看以了解如何执行此操作？简单的实现比目前的速度更重要.

补充:感谢您的评论.为了清楚起见,我正在寻找从指定的起始节点到指定的终端节点的最佳K方法,没有其他共同的节点.我需要全球最优; 顺序找到最佳和删除节点不会给出满意的结果.这个:https://en.wikipedia.org/wiki/Yen%27s_algorithm,给出了我所说的内容的味道,但在这种情况下,它需要非负边缘成本,它还允许共享节点.

我偶然发现了着名的Yen对Bellman-Ford算法的优化,这是我最初从维基百科得到的,然后我在练习部分的几本教科书中找到了相同的改进(例如,这是Cormen的24-1问题和在Sedgewick的网络练习N5 "算法").

这是改进:

Yen的第二个改进首先在所有顶点上分配一些任意线性顺序,然后将所有边的集合划分为两个子集.第一个子集Ef包含所有边(vi,vj),使得i <j; 第二个,Eb,包含边(vi,vj),使得i> j.按照v1,v2,...,v | V |的顺序访问每个顶点,从Ef中的那个顶点放宽每个输出边缘.然后按照v | V |,v | V | -1,...,v1的顺序访问每个顶点,从Eb中的那个顶点放宽每个输出边缘.算法的主循环的每次迭代,在第一次迭代之后,将至少两个边缘添加到边缘集合,其宽松距离匹配正确的最短路径距离:一个来自Ef,一个来自Eb.这种修改从| V |减少了算法主循环的最坏情况迭代次数 - 1到| V |/2.

不幸的是,我没有设法找到这个绑定| V |/2的证明,而且,似乎我找到了一个反例.我确信我错了,但我看不清楚到底在哪里.

反例只是一个路径图,顶点标记为1到n和初始顶点1.(因此,对于i,E = {(i,i + 1)}的范围从1到n-1).在这种情况下,前向顶点集合等于E(E_f = E),后向顶点集合只是空集合.算法的每次迭代仅添加一个正确计算的距离,因此算法在n-1时间内完成,这与提出的约束n/2相矛盾.

我究竟做错了什么？

UPD:所以这个错误非常愚蠢.我没有考虑通过顶点的迭代,考虑迭代直接更新路径成本.我不是删除这个主题,因为有人对它进行了投票,以防这种改进对某些人来说很有意思.