Bellman Ford Implementation and simultaneously relaxation

Question

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?

Why do you have both java and c++ tags. We frown upon tag-spamming here. — NomadMaker

Deepak Tatyaji Ahire Deepak Tatyaji Ahire · Accepted Answer · 2020-12-06T11:28:11

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 Implementation and simultaneously relaxation

1 Answers