# Bellman-Ford Algorithm

The Bellman–Ford algorithm finds shortest paths from a starting node to all nodes of the graph.

The upgrade of BF Algorithm is Dijkstra’s Algorithm.

- But it seems that there are good uses for bellman ford, because it works with negative weights while djikstra’s does not

### Implementation

Code assumes that the graph is stored as an edge list edges that consists of tuples of the form $(a,b,w)$, edge from node $a$ to node $b$ with weight $w$.

Time complexity is $O(ne)$

Negative Edges

Bellman-Ford works with negative edge weights (but no negative cycles). This doesn’t work with Dijkstra’s Algorithm.

From CS341

### Shortest Path Faster Algorithm (SPFA) Algorithm

The SPFA algorithm (”Shortest Path Faster Algorithm”) is a variant of the Bellman–Ford algorithm, that is often more efficient than the original algorithm.

### Proof

Let $δ_{i}(s,x)$ be the shortest path from $s$ to $x$ with at most $i$ edges.

If $δ(s,u)≤d[u]$ and $δ(s,v)≤d[v]$ before relaxation, then $δ(s,v)≤d[v]$ post-relaxation.