# graphs – Prove Edited Algorithm of Bellmanâ€“Ford?

I am stuck on this question for a week and hope to get some help:

Algorithm:

Given 2 sided Graph $$G(L,R,E)$$, a weight function and a root vertex $$s$$:

1. Define $$E1$$ as the group of edges connecting vertex from $$L$$ to $$R$$
(the rest are in $$E2$$ Group).

2. For each vertex $$v$$, Let
$$d(v)=infty$$ except $$d(s)=0$$ 3) Do $$(|L|+|R|)/2$$ (round floor)
iterations of the following:

Check Every edge in the graph, if d(v)>d(u)+w(u,v) then let
d(v)=d(u)+w(u,v)

Prove that if there is no circular path with total negative weight in
$$G$$, then the given algorithm returns for each vertex $$v$$ the minimal
weight of a path from s to $$v$$.

My try:

• For every vertex $$v$$ we can conclude that there is a shortest path from $$s$$ which is simple (no vertex appears twice, else we are getting a contradiction to the fact that there is no negative circular paths)

• The difference between number of edges from E1 and E2 is no more than 1

• For every simple and short path $$P$$ there is no more than $$(|L|+|R|)/2$$ (round floor) edges from $$E1$$ (and the same for $$E2$$).

Claim: For every vertex $$v$$ if there is a shortest path $$P$$ from $$s$$ to $$v$$, which contains $$k$$ edges from $$E1$$ then at the end of $$k$$-th iteration $$d(v)=|P|$$ ie the algorithm’s calculation is correct.

Proof: By induction on $$k$$.

But As I progressed it seemed that the claim doesn’t cover all cases (Thus it’s wrong). For example, it worked when $$v$$ is in $$R$$ group but failed To help prove the case when $$v$$ is in $$L$$ group.