I'm not sure this is the right community to ask this question, so feel free to move or close the discussion and point me to the right community.
I was wondering whether the Bellman-Ford (BF) algorithm can be seen as a contractive function, and hence admits a unique fixed point by the Banach's fixed-point theorem.
The BF algorithm is typically used to find shortest paths from a single source $s$ to any other node $u$ in a graph $G=(V, E)$, where V and E are vertices and edges. First of all, the BF update rule can be written as:
$T(d)_u = d_u = \min\{d_u, \min\{ d_v + w_{vu} : \forall v \in N(u) \}\}$
where $T: \mathbb{R}^{|V|} \rightarrow \mathbb{R}^{|V|}$ is the BF update rule, $N(u)$ represents the neighbourhood of node $u$, $w_{vu}$ is the edge weight from node $v$ to node $u$, and $d$ is initialized with $0$ for the source node (i.e., $d_s = 0$) and $\infty$ otherwise. Hence, if we consider the domain to be the space of vector distances, BF does have a fixed-point that corresponds to the optimal solution $d^*$ to which it converges in at most $|V| - 1$ steps (and from that point onwards, $T(d^*) = d^*$).
However, I'm unsure of how to formally prove that BF is a contractive function (if possible at all). I tried to prove on my own (unsuccessfully) that:
$||T(d) - T(d')||_p \leq ||d - d'||$
holds, where $d$ and $d'$ are the vector of distances of two successive iterations of Bellman-Ford. However, contractive functions usually require $d$ and $d'$ to be any input, so I am unsure that would even help.
Does anyone have any intuitions on how to prove that BF satisfies the contractive mapping theorem, or if this is possibile at all? Any references would be appreciated too.
It is possible for Bellman–Ford to not terminate at all, if there is a negative cycle.
Even when restricted to nonnegative edge weights, it is possible to set initial distances such that they form different fixed points, as the algorithm blindly takes the minimum of (sum of incoming edge weight and neighbour distance) and (this vertex's distsnce) – a trivial example is where all edges are of weight $1$ and all distances are $0$.
Since we can make multiple fixed points for some networks, Bellman–Ford cannot be a contractive mapping.