Bellman-Ford algorithm for shortest paths and potentials

Bellman-Ford shortest paths algorithm. Finding minimal distances in directed graphs, when some arc lengths are negative, cannot be done by Dijkstra’s algorithm (at least not without some preparation). Moreover, it is obvious that one cannot even define the minimal distances when the digraph has a negative length cycle.
While negative length paths look artificial, they arise naturally in modeling (say, a driver has to pay to use certain stretches of the road, but is paid for driving up other stretches) and algorithms, not the least in Hungarian method for weighted bipartite matching.

Let $\Gamma=(V,A)$ be a directed graph and $\ell:A\to \mathbb{R}$ a length function on the arcs of $\Gamma.$ Suppose we are interested in the shortest, w.r.t. $\ell,$ (directed) paths from $v\in V$ to all the vertices of $\Gamma$ (reachable from $v,$ that is). We define $d_k(u)$ to be the minimal length of at most $k$ -arc path from $v$ to $u\in V.$

Certainly, $d_0(v)=0$ (as our graph does not have a negative length cycle) and $d_0(u)=\infty$ for all $v\neq u\in V.$ Then, by induction,

$d_k(u)=\min (d_{k-1}(u),\min_{(w,u)\in A}d_{k-1}(w)+\ell(w,u)).$

That’s good, but can $k$ grow arbitrarily? Well, if a walk to $u$ visits a vertex more than once, this means it contains a cycle — unless this cycle has negative length (and we don’t allow it here) it can be removed from the walk, and it will not increase walk’s length. Thus without loss in generality, a shortest path to $u$ has at most $|V|$ vertices, and so $d_n(u)$ is the distance from $v$ to $u.$

Thus in at most $O(|V||E|)$ operations we will find the distances from $v$ to all the vertices of $\Gamma.$

Excercise. Modify the procedure to do a simultaneous computation of the distances from each $v\in V$ to all $u\in V,$ i.e. the distance matrix, in $O(n^3)$ operations.

Potentials. In this setting, a useful concept is that of potential, a function $p:V\to\mathbb{R}$ such that

$\ell(u,v)\geq p(v)-p(u),\quad$ for all $(u,v)\in A.$

When all the arc lengths are nonnegative, the zero function $v\mapsto 0$ is a potential. When there are negative length arcs, a potential can be used to adjust the distance function so that the new one is nonnegative, and a path is shortest w.r.t. to the new function iff it is shortest w.r.t. the old one: namely, set $\ell'(u,v)=\ell(u,v)-p(v)+p(u)$ for all arcs $(u,v).$ Indeed, when we compute the $\ell'$ -length $\ell'(P)$ of the path $P$ between $x$ and $y,$ we see that $\ell'(P)=\ell(P)-p(y)+p(u).$

Constructing a potential. Attach to $\Gamma$ an extra vertex $v_0$ and join it with the vertices $v$ of $\Gamma$ by arcs $(v_0,v)$ of length 0. Run Bellman-Ford algorithm for the distances $d(v_0,v),$ and set $p(v)=d(v_0,v).$ As for any arc $(u,v)$ one has $p(v)\leq p(u)+\ell(u,v),$ we indeed obtain a potential.

Again, here we assume that there are no negative length cycles in $\Gamma$ – indeed, otherwise a potential does not exist (this can be proved by summing the inequalities $\ell(u,v)\geq p(v)-p(u)$ along a cycle.)

Like this:

One blogger likes this post.

Tags: combinatorics, graph theory, MAS324, MAS445

This entry was posted on 18 September, 2009 at 2:35 and is filed under undergrad maths. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Bellman-Ford algorithm for shortest paths and potentials”

2010 in review – Happy New Year! « Equatorial Mathematics Says:
2 January, 2011 at 22:01 | Reply
[...] Bellman-Ford algorithm for shortest paths and potentials September 2009 [...]

Equatorial Mathematics