Most of us know Prim's or Dijkstra's algorithm for finding the shortest path though a graph or network, but did you know that this classic algorithm breaks down if the edge weights, the lengths that make up the path, are negative.

Networks are a natural generalization of concrete situations such as a road or rail network. A common problem is to find the shortest path connecting two points or network nodes and it comes as a surprise to many that this can be solved efficiently using an algorithm.

The algorithm in question was first developed in 1930 by Czech mathematician Vojtěch Jarník, then developed independently in 1957 by computer scientist Robert C. Prim and was rediscovered by in 1959 by Edsger Dijkstra. In its most efficient form it achieves a run time of O(e+vlogv) where e is the number of connections and v is the number or points.

This is a very important algorithm that makes some optimization problems easier. The problem is that it only works if the distances between the points are all positive. Negative distances are natural in many problems where the distances represent costs or profits say. The best we can do using a traditional algorithms is the Bellman-Ford algorithm which runs in O(ev) - too slow for many practical applications but it is indeed used.

The Bellman-Ford algorithm is related to the problem of reinforcement learning which is at the heart of many of the current breakthroughs in AI. We could do with discovering something better to apply to bigger systems. This is what a researchers from the University of Copenhagen and Rutgers University have done in reducing the runtime to essentially linear.

The good news is that the method isn't overly complicated. It works by using the time-honoured technique of reducing the problem to a collection of smaller problems. In this case the idea is to break the network down into a number of low-diameter sub-networks. In this context low-diameter means that the points are close to one another. After breaking the network into smaller networks these can be solved using the Bellman-Ford algorithm and this is used to restructure the complete network so that it can be solved using Dijkstra's algorithm. As the initial decomposition is done randomly, the performance is only an average, but it is still a big improvement over Bellman-Ford.

If you want to know more then take a look at the video:

And if you want the fine detail, read the paper.

More Information

Negative-Weight Single-Source Shortest Paths in Near-linear Time by Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen

Related Articles

The Minimum Spanning Tree - Prim's Algorithm

Travelling Salesman - A Movie About P=NP

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info