About Bellman-Ford Algorithm for the single-source shortest paths

Pseudo-Code:
      BELLMAN-FORD$(G,w,s)$

1. INITIALIZE-SINGLE-SOURCE$(G,s)$
2. for $i=1$ to $|G.V|-1$
3.       for each edge $(u,v)$ in $G.E$
4.             RELAX$(u,v,w)$
5. for each edge $(u,v)$ in $G.E$
6.       if $v.d >u.d+w(u,v)$
7.             return FALSE
8. return TRUE 

Explanation:

      INITIALIZE-SINGLE-SOURCE$(G,s)$

1. for vertex $v$ in $G.V$
2.       $v.d = \infty$
3.       $v.\pi = NIL$
4.  $s.d = 0$

And,

      RELAX$(u,v,w)$

1. if $v.d>u.d+w(u,v)$
2.      $v.d = u.d+w(u,v)$
3.       $v.\pi = u$

Here, $w$ is the weight function, $G$ is the graph, and has $V$ as it's vertices, and $E$ as it's edges.

Now, the BELLMAN-FORD algorithm can be divided into two parts:

1. Lines 2-4: Makes the predecessor graph. Basically it would compute the needed distances, if the graph doesn't contain any negative-weight cycles.
2. Lines 5-8: Checks whether the graph has a negative-weight cycle or not.

Lines 2-4:

What we're doing here: $|V|-1$ times relaxing all the edges.

Why does it work?
Path relaxation property:

If $p = <v_0,v_1,...,v_k>$ is the shortest path from $s=v_0$ to $v_k$, and we relax the edges of $p$ in the order $(v_0,v_1),(v_1,v_2),...,(v_{k-1},v_k)$, then $v_k.d=\delta(s,v_k)$. This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.

So, basically, even if we add some other relaxations in between this order of relaxations, then too we'll have the same shortest path from $v_0$ to $v_k$.

Here, we're sure that in the first iteration we'll relax $(v_0,v_1)$, regardless of the order of relaxation. Then in the second iteration, we'll relax $(v_1,v_2)$ for sure. Thus in the end, the order is followed, and we get the shortest path from $v_0$ to $v_k$.

So, in the end, we'll get the right path to all the connected vertices.
   
Lines 5-7:

This part is used to check whether there is some negative-weighted cycle in $G$.

This is done via checking $v.d >u.d + w(u,v)$. If it's TRUE, then we've a cycle, and we return a FALSE. Otherwise, it's okay, and we return a TRUE.

The point of doing this comparison:
Well, assume that we've a negative-weight cycle $c = <v_0,v_1,...v_k>$ in $G$, but BELLMAN-FORD still returns a TRUE value. Now, that would mean that $$v.d \leq u.d+ w(u,v)\text{ (line 6's inverse)} $$
Now, doing this for all the vertices of the cycle:
$$\sum_{i=1}^{k}v_i.d \leq \sum_{i=1}^{k}v_{i-1}.d + \sum_{i=1}^{k}w(v_{i-1},v_i) $$

But, since $v_0=v_k$ for a cycle, $\sum_{i=1}^{k}v_i.d = \sum_{i=1}^{k}v_{i-1}.d$. Because of which we get $$0 \leq \sum_{i=1}^{k}w(v_{i-1},v_i)$$ which is contradictory, since $c$ is a negative weight cycle.
This is the reason why this comparison works.

Running time:
Due to lines 2-4, the running time obviously goes to $O(|V||E|)$.