Code covered by the BSD License

### Highlights from The Bellman-Ford-Moore Shortest Path Algorithm

4.0
4.0 | 2 ratings Rate this file 17 Downloads (last 30 days) File Size: 224 KB File ID: #38129 Version: 1.11

# The Bellman-Ford-Moore Shortest Path Algorithm

### Derek O'Connor (view profile)

11 Sep 2012 (Updated )

A simple, efficient sparse implementation of the original Bellman-Ford-Moore Shortest Path Algorithm

File Information
Description

Over the years I have looked at many Shortest Path FEX submissions. Most,if not all of these, were implementations of Dijkstra's algorithm for dense adjacency matrices.

These submissions had very limited usefulness because most real graph problems are sparse and most can be solved much more efficiently by a variant of the Bellman-Ford-Moore (BFM) algorithm which predates Dijkstra by 4 or 5 years. Better still, BFM is robust in the sense that it can handle negative arc-weights and detect and find negative cycles. Dijkstra cannot do this and for this reason is not considered robust.

It was for these reasons and others that I decided to (try) to write the simplest possible Matlab function for shortest paths. This forced me to use the simplest possible data structures to represent the problem and its solution, in Matlab: the graph G is represented by a list of m arcs (head, tail, weight) or (u,v,duv); the solution is represented by a tree p which is an n-vector of parent "pointers"; the n-vector D is the shortest path distances. Thus the path from node u to the root r is u,p(u),p(p(u)), ... , p(r). The length of this shortest path is D(u). We can see that the space used is S = No. of arcs = m (nnz) + 2*n fixed-sized boxes. You can't get lower than that.

The latest version of the notes on this algorithm is available at:

http://www.scribd.com/derekroconnor4276

MATLAB release MATLAB 7.6 (R2008a)
03 Apr 2016 Faezeh Fallah

### Faezeh Fallah (view profile)

23 Apr 2015 aa 1987

### aa 1987 (view profile)

Dear Derek,
How can I use the code to detect negative cycles in the graph. Could you provide an example code ?

Comment only
08 May 2013 Roland

### Roland (view profile)

Dear Derek,
Do I understand correctly when I say that your function is only capable of computing the shortest path between a root and all other nodes. I am looking for a function that efficiently computes shortest paths between all nodes in a subset of the nodes of the whole graph.
Do I understand your code correctly when I say the following:
- I would have to call the function multiple times (for each root). It is not possible to specify r as a vector of roots? In other words, this algorithm does not save any info when you have to compute path from multiple roots.
- All computation spent on shortest paths to nodes that I do not need is lost. Is this really necessary (i.e. inherent to the Bellman-Ford algorithm) or could this could become faster if it is adapted to the situation I need it for?
Kind regards.
Roland

Comment only
11 Mar 2013 Matlab2010

### Matlab2010 (view profile)

Derek, I sent you an email outlining the real problem data/context etc.

Comment only
08 Mar 2013 Derek O'Connor

### Derek O'Connor (view profile)

I would be grateful if you would post or send me your results for these REAL problems.

For example, I have not been able to find the official optimum solutions to the problems. This makes me uneasy.

Comment only
08 Mar 2013 Matlab2010

### Matlab2010 (view profile)

My mistake! Yes I can see you have written it in.

Excellent algo that works straight out of the box.

07 Mar 2013 Derek O'Connor

### Derek O'Connor (view profile)

This file is not there because I did not have room for the larger files on my website. I pointed this out at the start of TestBFNOTMaps.m

All the USA files are available here:

Comment only
07 Mar 2013 Matlab2010

### Matlab2010 (view profile)

I try to run TestBFNOTMaps.m and get the error

Unable to read file spusaNE: No such file or directory.

where is this file? Not in the zip file.

Comment only
02 Nov 2012 Derek O'Connor

### Derek O'Connor (view profile)

I have corrected an error in BFMSpathOT.m The two variables 'head' and 'tail' were switched which resulted in the directed arcs of the network being reversed.

This means that the old version gave the wrong answers [p D]. However, this change does not affect the analysis and running time of the algorithm.

Comment only
02 Nov 2012 Derek O'Connor

### Derek O'Connor (view profile)

The updated Matlab function BFMSpathOT.m can be found at:

http://www.scribd.com/doc/105903247/O-Connor-The-Bellman-Ford-Moore-Shortest-Path-Algorithm.m

Comment only
19 Oct 2012 Derek O'Connor

### Derek O'Connor (view profile)

I have an important update to this submission which corrects an error but the UPDATE process fails each time I use it.

Derek O'Connor

Comment only
12 Sep 2012 1.2

Corrected minor typos

12 Sep 2012 1.3

12 Sep 2012 1.4

12 Sep 2012 1.7

12 Sep 2012 1.8

Minor code modification

14 Sep 2012 1.9

Added an 11-page paper of notes and two test functions: one for random networks and one for real road networks

17 Sep 2012 1.10

Updated notes and results of tests.

18 Sep 2012 1.11