bellman-ford algorithm

$\text{[math]}$ is used to find distances and [[blk:1683775638][negative cycle]]s in directed graphs.

the difference between dijkstra's algorithm and bellman-ford is that bellman works on all real-valued weights and can handle negative weights while dijkstra cant.

negative cycles prevent some challenges when dealing with weighted graphs, as they can form cycles with a weight of $\text{[math]}$ .

consider the following graph whose weights function is taken from the real number line
$\text{[math]}$ at first glance the distance from $\text{[math]}$ to $\text{[math]}$ seems to equal 10, but if we were to go back and forth from the node $\text{[math]}$ to $\text{[math]}$ we'd find that on each step the distance decreases by -2, which would mean that the distance equals $\text{[math]}$ , this is why when dealing with negative weights we only consider directed graphs

the bellman ford algorithm works by choosing a vertex and assigning infinity values to all the other vertices, then visit each edge and relax the path distances if they are inaccurate, this needs to be done $\text{[math]}$ times because in the worst case, a vertex's path length might need to be readjusted $\text{[math]}$ times
$\text{[math]}$

let $\text{[math]}$ be a graph, the vertex $\text{[math]}$ is reachable from $\text{[math]}$ if in $\text{[math]}$ there is a path from $\text{[math]}$ to $\text{[math]}$ .

let $\text{[math]}$ be a directed graph with no negative cycles, let $\text{[math]}$ be a vertex in $\text{[math]}$ . for each $\text{[math]}$ , if in $\text{[math]}$ there is a path from $\text{[math]}$ to $\text{[math]}$ , then in $\text{[math]}$ there is a minimal simple path from $\text{[math]}$ to $\text{[math]}$ .

if $\text{[math]}$ is a simple path, the lemma follows trivially, if not, in $\text{[math]}$ there is atleast one cycle $\text{[math]}$ whose length isnt negative. let $\text{[math]}$ be the path received by cutting $\text{[math]}$ . in $\text{[math]}$ there is one cycle less than in $\text{[math]}$ , and its obvious that $\text{[math]}$ . we can continue with this proces until we get a simple path from $\text{[math]}$ to $\text{[math]}$ , $\text{[math]}$ , such that $\text{[math]}$ .
in a simple path no vertex repeats itself and so the number of simple paths from $\text{[math]}$ to $\text{[math]}$ is finite. since the number of simple paths in $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ is finite, one of them must be the one with the minimum length.

let $\text{[math]}$ be a directed real-number-weighted graph with no negative cycles, and let $\text{[math]}$ be some arbitrary vertex. for each vertex $\text{[math]}$ , we denote by $\text{[math]}$ the number of edges in the minimal path from $\text{[math]}$ to $\text{[math]}$ with the minimum number of edges.

let $\text{[math]}$ be a directed real-weighted graph with no negative cycles and let $\text{[math]}$ be some arbitrary vertex. if the bellman-ford algorithm is applied to $\text{[math]}$ starting at $\text{[math]}$ , then for each $\text{[math]}$ , after $\text{[math]}$ iterations in the first loop the demands of $\text{[math]}$ would have been met.

by "the demands of a vertex" we refer to a correct configuration of values for $\text{[math]}$

a proof by induction on $\text{[math]}$ (loop index) that for all $\text{[math]}$ if $\text{[math]}$ the demands of $\text{[math]}$ are met:
base ( $\text{[math]}$ ): the only vertex for which there is an empty path (a path with 0 edges) from $\text{[math]}$ to it, is the origin vertex $\text{[math]}$ . in $\text{[math]}$ we have $\text{[math]}$ , and since in $\text{[math]}$ there are no negative cycles then $\text{[math]}$ . the second demand of the vertex is emptily correct.
induction hypothesis ( $\text{[math]}$ ): we assume that for all $\text{[math]}$ , if $\text{[math]}$ , the lemma holds true.
we have to show that for all $\text{[math]}$ such that $\text{[math]}$ the demands of the vertex $\text{[math]}$ are met.
let $\text{[math]}$ be an arbitrary vertex in $\text{[math]}$ such that $\text{[math]}$ and let $\text{[math]}$ be a minimal simple path from $\text{[math]}$ to $\text{[math]}$ . let $\text{[math]}$ be the subpath that is received by cutting the last edge from $\text{[math]}$ . $\text{[math]}$ is a subpath of a simple minimal path and so it is minimal and simple too, it also has $\text{[math]}$ edges. according to the induction hypothesis, after $\text{[math]}$ iterations in the loop the demands of $\text{[math]}$ are met.
one of the relaxing steps that are done in the $\text{[math]}$ -th iteration in the first loop is a relaxing step over $\text{[math]}$ . after this relaxing step the demands of $\text{[math]}$ would be met.

let $\text{[math]}$ be a directed real-weighted graph with no negative cycles and let $\text{[math]}$ , if the bellman-ford algorithm was applied to $\text{[math]}$ , starting from $\text{[math]}$ , after $\text{[math]}$ iterations, for each vertex $\text{[math]}$ the demands of $\text{[math]}$ would be met.

since for all $\text{[math]}$ , $\text{[math]}$ , the claim follows trivially from lem-bellf-2

let $\text{[math]}$ be a directed real-weighted graph, let $\text{[math]}$ be an arbitrary vertex, assume in $\text{[math]}$ there is a negative cycle reachable from $\text{[math]}$ . if bellman-ford is applied to $\text{[math]}$ starting at $\text{[math]}$ , then during the checking process we find a non-empty relaxing step

assume in contradiction that in $\text{[math]}$ there is a negative cycle $\text{[math]}$ that is reachable from $\text{[math]}$ , but during the validation process in the second loop we dont find a non-empty relaxing step.
since $\text{[math]}$ is reachable from $\text{[math]}$ , after at most $\text{[math]}$ iterations in the first loop, $\text{[math]}$
given that along $\text{[math]}$ there arent any relaxing steps, for each edge $\text{[math]}$ :
$\text{[math]}$ we write these inequalities one after another and get:
$\text{[math]}$ if we were to summarize those inequalities along the negative cycle and recall that $\text{[math]}$ we get:
$\text{[math]}$ the first two sums are equal because we're dealing with the same vertices and so:
$\text{[math]}$ which contradicts with the assumption that $\text{[math]}$ is a negative cycle

the bellman-ford algorithm recognizes the existence of a negative cycle and incase there does not exist such a cycle it correctly computes the distances of the vertices from the origin vertex and computes a distance tree.

the correctness of the algorithm in case the input graph contains no negative cycles was proved in lem-bellf-3, in lem-bellf-4 it was proved that if in $\text{[math]}$ there exists a negative cycle $\text{[math]}$ , then during the validation process, atleast one non-empty relaxing step is found.

the time complexity of the algorithm is $\text{[math]}$ .
for dense graphs, the time complexity of the algorithm goes up to $\text{[math]}$ .