graphs – Prove Edited Algorithm of Bellman–Ford?

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


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

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.