Bellman-Ford Algorithm

1. For each ,
   d(s) = 0
2. for to |V|-1

   for each edge

   if d[v]>d[u]+w(u,v)

   then

3. for each edge
   

   if d[v]>d[u]+w(u,v)

   then no solution

Lemma: always.
First part of Lemma 25.5, section 25.1

Initially true.

Let v be first vertex for which , and let u be vertex that cause d[v] to change: d[v]=d[u]+w(u,v)

Then

(Triangle inequality)
(v is first violation)

contradicts d[v]=d[u]+w(u,v) (above).

Lemma: Bellman-Ford Algorithm is correct.