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.)

Advertisements

Tags: , , ,

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

  1. 2010 in review – Happy New Year! « Equatorial Mathematics Says:

    […] Bellman-Ford algorithm for shortest paths and potentials September 2009 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: