# Prove Edited Algorithm of Bellman–Ford?

Please Note: I forgot a small detail which caused the algorithm to be incorrect, please read the new version and thanks for pointing that.

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

Algorithm:

Given 2 sided Graph ie bipartite 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) = ∞ except d(s) = 0
3. Do (|L|+|R|)/2 (round floor) iterations of the following:

Check Every edge in the graph, while finishing all edges > in E1 and only then moving on to E2: 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.

Thanks in advance for any help

New contributor
coolmo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Any help please on what should the claim be? (as mine is wrong or isn't helpful to prove correctness) – coolmo Jun 5 at 21:35
• Prove by induction on the number of iterations that at the end of iteration $i$ all values $d(u)$ where $u$ is at distance at most $2i$ from $s$ are exactly the distance from $s$ to $u$ in $G$. – Steven Jun 5 at 21:43
• Another, less precise, way to show the result is noticing that each iteration of your algorithm corresponds to two iterations of the Bellman-Ford algorithm. Since the correctness of the Bellman-Ford algorithm does not depend on the order in which edges are examined (which can be different between iterations) we are free to choose our own edge order. – Steven Jun 5 at 23:10
• In details, an iteration of your algorithm yields the same distances obtained by performing 1) an iteration of Bellman-Ford in which edges in $E_2$ are examined before those in $E_1$ (here no distance is updated while examining $E_2$), and 2) and iteration of Bellman-Ford in which edges in $E_1$ are examined before those in $E_2$ (no distance is actually updated while examining $E_1$). – Steven Jun 5 at 23:10
• @Steven I tried induction and that's where I stuck, I said let P be the shortest path from u to v of lengh n, ie P: u->...->w->v. I said let's look at u->...->w which is of length n-1 so according to the assumption we know that d(w)=s(u,w). But how this can help me say that d(v)=s(u,v)? I proved that at every moment s(s,v)<=d(v) if that helps. Thanks – coolmo Jun 6 at 0:34

Let $$D(t,i)$$ denote the length of the shortest among the path from $$s$$ to $$t$$ in $$G$$ that use at most $$i$$ edges.

We will focus on the generic $$i$$-th iteration of the algorithm and show that:

• (i) after all the edges in $$E_1$$ have been considered, we must have $$d(t) \le D(t, 2i)$$ for each vertex $$t \in R$$.
• (ii) after all the edges in $$E_2$$ have been considered, we must have $$d(t) \le D(t, 2i)$$ for each vertex $$t \in L$$.

As an edge case we consider the $$0$$-th iteration to be completed immediately before the start of the for loop.

The proof is by induction on $$i$$. The base case $$i=0$$ is trivially true since the only vertex at hop-distance $$0$$ from $$s$$ is $$s \in L$$ itself and the algorithm explicitly sets $$d(s) = 0 = D(s, 0)$$.

Consider now $$i > 0$$. If $$t=s$$ we know, by induction hypothesis, that after iteration $$0$$ we have $$d(s) \le D(s,0) \le D(s, 2i)$$. Therefore, we restrict ourselves to the case in which $$t \neq$$ s and $$D(t, 2i)$$ is finite. Let $$(v,t)$$ be the last edge in any shortest path from $$s$$ to $$t$$ in $$G$$ that uses at most $$2i$$ edges.

If $$t \in R$$ then $$v \in L$$ and all paths to $$v$$ have even hop-length. Therefore, when $$(v,t) \in E_1$$ is considered, we have $$d(v) \le D(v, 2(i-1))$$ by induction hypothesis and hence: $$D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2(i-1)) + w(v,t) \ge d(v)+w(t).$$ This ensures that, after examining $$(v,t)$$ in iteration $$i$$ we must have $$d(t) \le d(v)+w(t) \le D(t, 2i)$$ and proves (i).

If $$t \in L$$ then $$v \in R$$ and all paths to $$v$$ have odd hop-length. When $$(v,t) \in E_2$$ is considered we have $$d(v) \le D(v, 2i)$$ (this follows from (i), which we just proved). Therefore: $$D(t, 2i) = D(v, 2i-1) + w(v,t) = D(v, 2i) + w(v,t) \ge d(v) + w(v,t).$$ Therefore, after $$(v,t)$$ is examined, we must have $$d(t) \le D(t, 2i)$$. This proves (ii) and concludes the proof by induction.

At this point we just need to notice that, the above claim, implies that at the end of the algorithm $$d(t)$$ is at most $$D(t, 2 \lfloor (|L|+|R|)/2\rfloor) \le D(t, |L|+|R|-1)$$, where $$D(t, |L|+|R|-1)$$ is exactly the distance from $$s$$ to $$t$$ in $$G$$. Moreover, all (finite) distances $$d(t)$$ computed by the algorithm correspond to the length of an actual path to $$t$$ in $$G$$, showing that $$d(t)$$ is also not smaller than the distance from $$s$$ to $$t$$ in $$G$$.

This part of the answer refers to a previous version of the question in which the Algotithm did not prescribe any particular order in which to consider the edges

If by 2-sided graph you mean bipartite graph, then the algorithm is wrong.

As a counterexample consider the graph $$G=(L \cup R, E)$$ where $$L = \{s, \ell\}$$, $$R =\{r\}$$ $$E=\{(s,r), (r, \ell)\}$$, and all edge weights are $$1$$. The algorithm will perform $$\left\lfloor \frac{|L|+|R|}{2} \right\rfloor = 1$$ iteration. Since there is no prescribed order in which the edges are considered, we can look at the case in which $$(r, \ell)$$ is considered before $$(s, \ell)$$.

When $$(r, \ell)$$ is examined, the condition of the if statement is not satisfied, so $$d(\ell)$$ is not updated. Moreover, when $$(s, r)$$ is considered only $$d(r)$$ can possibly be updated, so $$d(\ell)$$ is unchanged.

This shows that at the end of the algorithm $$d(\ell) = + \infty$$ but the distance between $$s$$ and $$\ell$$ in $$G$$ is $$2$$.

• So sorry my fault, the actual question said to run E1 before E2 and I ignored that by mistake. Please keep this as it's helpful and hope if you can help me fix my proof and continue it. – coolmo Jun 5 at 20:00