The Bellman-Ford-Moore Shortest Path Algorithm

A simple, efficient sparse implementation of the original Bellman-Ford-Moore Shortest Path Algorithm
3K Downloads
Updated 18 Sep 2012

View License

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

Cite As

Derek O'Connor (2024). The Bellman-Ford-Moore Shortest Path Algorithm (https://www.mathworks.com/matlabcentral/fileexchange/38129-the-bellman-ford-moore-shortest-path-algorithm), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2008a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Construction in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.11.0.0

Added a Scribd link for the notes on this algorithm.

1.10.0.0

Updated notes and results of tests.

1.9.0.0

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

1.8.0.0

Minor code modification

1.7.0.0

Eliminated comments

1.4.0.0

Added a minor note.

1.3.0.0

Eliminated irrelevant comments

1.2.0.0

Corrected minor typos

1.0.0.0