Bellman Ford实施并同时放松 [英] Bellman Ford Implementation and simultaneously relaxation

问题描述

最近，我贝尔曼福特和一些事实看到以下问题:

我们知道Bellman-ford算法会检查每个步骤中的所有边缘，并且对于每个边缘，如果d(v)> d(u)+ w(u，v)成立，则 d(v)正在更新. w(u，v)是边缘(u，v)的权重，而 d(u)是最佳查找路径的长度顶点 u .如果在任何步骤中没有针对任何顶点的更新，则使用算法终止.

为了找到图G中具有 n 个顶点的顶点 s 的所有最短路径，此算法在 k< k;之后终止.n 迭代.

以下事实是正确的.

从 s 开始的所有最短路径中的边数最多为 k-1

在此

解决方案

最终算法 BellmanFordFinal(s)是上述所有3种算法的优化版本.

优化1:

在书中，传奇人物Jeff Erickson教授解释了如何通过消除算法的最后3行的缩进来优化Bellman提出的原始算法.

因为最外面的迭代只对每个边 u-> v 进行一次考虑，所以处理它们的顺序并不重要.

优化2:

最后两行将索引 i-1 更改为 i ，这使得算法可以通过正确计算值(最短路径)来更快地工作).

优化3:

不需要的二维DP数组将转换为1维.

因此，请使用名为 BellmanFordFinal(s)的最终算法.

我们需要在 N-1 次上运行最外面的循环，这一事实始终是正确的，并且与任何实现无关，因为从源到目标的最长最短路径将是对于线性图， N-1 ，其中N是图中的节点数.

回答您有关 k-1

的问题

从s开始的所有最短路径中的边数最多为k-1

以上陈述取决于您算法的实现.

如果添加一个if条件以在没有任何一条边进一步放松时中断最外层循环，则该语句为false.

否则，这是真的.

看看我在 https://cp-algorithms.com上找到的以下实现/graph/bellman_ford.html :

  voidsolve(){向量< int>d(n，INF)；d [v] = 0;为了 (;;){bool any = false;对于(int j = 0; j< m; ++ j)如果(d [e [j] .a]< INF)如果(d [e [j] .b]> d [e [j] .a] + e [j] .cost){d [e [j] .b] = d [e [j] .a] + e [j] .cost;任何= true;}如果(！any)中断；}//例如在屏幕上显示d} 

变量 any 用于检查它们是否在任何迭代中完成了松弛.如果没有完成，请打破循环.

因此，例如，当k ＝ 2并且最长的最短路径中的边数为3时，可能会终止循环.现在，3 ＜＝ 2-1.

Recently I see this question Bellman Ford and Some Facts as follows:

We know the bellman-ford algorithms check all edges in each step, and for each edge if, d(v)>d(u)+w(u,v) was hold then d(v) being updated. w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex u. if at any step there is no update for any vertexes, the algorithm terminate.

for finding all shortest path from vertex s in graph G with n vertexes this algorithm terminate after k < n iteration.

The following fact is true.

number of edges in all shortest paths from s is at most k-1

in this Book we have 3 implementation (some optimization) of BFord. My question is that if we have simultaneously relaxation which algorithm of these should be used, and by using it the above fact should be true? or not in general the above fact is true?

解决方案

The final algorithm, BellmanFordFinal(s) is the optimised version of all the 3 mentioned algorithms.

OPTIMIZATION 1:

In the book, the legendary Prof. Jeff Erickson has explained, how the original algorithm presented by Bellman is optimised by removing the indentation of the last 3 lines in the algorithm.

Because the outermost iteration considers each edge u->v exactly once, the order in which they get processed, does not matter.

OPTIMIZATION 2:

The indices i-1 has been changed to i in the last 2 lines, which enables the algorithm to work more faster with correct computation of the values (shortest path).

OPTIMIZATION 3:

The 2 dimensional DP array is converted to 1 dimension as it was needless.

Therefore, use the final algorithm, titled, BellmanFordFinal(s).

The fact that we need to run the outermost loop for N-1 times is always true and independent of any implementation, because, the longest shortest path from a source to destination will be N-1 in case of the linear graph, where N is the number of the nodes in the graph.

Answer to your concern about k-1

number of edges in all shortest paths from s is at most k-1

The above statement is dependent on the implementation of your algorithm.

If you add a if condition to break the outermost loop when none of the edges are further relaxed, then this statement is false.

Otherwise it is true.

Have a look at the following implementation I found on https://cp-algorithms.com/graph/bellman_ford.html:

void solve()
{
    vector<int> d (n, INF);
    d[v] = 0;
    for (;;)
    {
        bool any = false;

        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                if (d[e[j].b] > d[e[j].a] + e[j].cost)
                {
                    d[e[j].b] = d[e[j].a] + e[j].cost;
                    any = true;
                }

        if (!any) break;
    }
    // display d, for example, on the screen
}

The variable any is used to check if their is any relaxation done in any of the iteration. If not done, break the loop.

Therefore, it might happen that the loop gets terminated before, for example, when k=2 and the number of edges in the longest shortest path is 3. Now, 3 <= 2-1, does not hold correct.

这篇关于Bellman Ford实施并同时放松的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！