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$:
Define $E1$ as the group of edges connecting vertex from $L$ to $R$
(the rest are in $E2$ Group).
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$.
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.