**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 be a directed graph and a length function on the arcs of Suppose we are interested in the shortest, w.r.t. (directed) paths from to all the vertices of (reachable from that is). We define to be the minimal length of at most -arc path from to

Certainly, (as our graph does not have a negative length cycle) and for all Then, by induction,

That’s good, but can grow arbitrarily? Well, if a walk to 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 has at most vertices, and so is the distance from to

Thus in at most operations we will find the distances from to all the vertices of

**Excercise.** Modify the procedure to do a simultaneous computation of the distances from each to all i.e. the distance matrix, in operations.

**Potentials.** In this setting, a useful concept is that of *potential*, a function such that

for all

When all the arc lengths are nonnegative, the zero function 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 for all arcs Indeed, when we compute the -length of the path between and we see that

**Constructing a potential.** Attach to an extra vertex and join it with the vertices of by arcs of length 0. Run Bellman-Ford algorithm for the distances and set As for any arc one has we indeed obtain a potential.

Again, here we assume that there are no negative length cycles in – indeed, otherwise a potential does not exist (this can be proved by summing the inequalities along a cycle.)

### Like this:

Like Loading...

*Related*

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.

2 January, 2011 at 22:01 |

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