We are given the following algorithm:
Input: bipartite graph G=(L,R,E), weight function w:E->Z and a source vertex s in L
Algorithm:
1) Define E1={(u,v) in E | u in L, v in R} and E2=E\E1
2) Initialize d(s)=0 and d(v)=inf for all vertices in L and R (except s)
3) Perform floor((|L|+|R|)/2) times:
a. Pass on all edges (u,v) in E1:
if d(v) > d(u) + w(u,v) then d(v) = d(u) + w(u,v)
b. Pass on all edges (u,v) in E2:
if d(v) > d(u) + w(u,v) then d(v) = d(u) + w(u,v)
4) Return d(v) for each vertex
This algorithm gives the shortest path from s to all other vertices and we are asked to prove its correctness. Now, as much as I can tell, the correctness proof should be exactly like Bellman-Ford's algorithm (using induction over the path's length), but I can't tell what is the change I am suppose to do in order to make it work for this algorithm.
I am not sure if I can ask question like these on here, but I've been on this for the past 4 days and I can't seem to see any difference from bellman-ford's correctness proof.
Any suggestions?
Thank you :)