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.