Shortest Path – Bellman Ford algorithm

Here are my notes on how to implement the Bellman Ford algorithm to find the shortest path of a graph:

This is along the lines of what Rob Conery describes in The Imposter’s Handbook. And here is my c++ implementation of this:

The above is a vertex oriented walk through the graph, where we visit each vertex and calculate the costs to every outwardly connected vertex. I have found it simpler to just walk through an array of edges, which cuts down some complexity:

To keep this simple, I left out the optimisation to break out of the outer loop when no more updates are made.

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *