Bellman-Ford shortest path algorithm Tips & Tricks

If you want to find out the shortest distance between a graph. Bellman Ford is one of the algorithms you can use.

To find more about Bellman-Ford algorithm check this Wiki :

And this great interactive site showing step-by-step process:

Now, in this post I’m not trying to :

• Explain how Bellman-Ford works
• Comparison between other shortest path algorithms

But, here are a few Tips.

Ironically, One of the main confusing points to me was, how do you get the shortest path by using Bellman-Ford. Wait a minute, isn’t that’s what the algorithm is supposed to do? Are we being ripped off?

Well, the algorithm is divided into two parts.

1. Calculating the graph weights
2. Calculating the shortest path

Most of the literature available is talking about the first part. You need to perform the additional step in second part to actually get the shortest path.

For that you need to keep track of trail of vertices.

See this pseudo/c++ code :

Now, the last line is interesting. For every single vertices ID which satisfies the condition, we store the previous vertices ID. It’s a simple key-value pair dictionary.

Side Tip : No matter how you get your graph data [if it’s a network traffic, edges on CAD model, geographic distances btw points etc]. It’s better to organize it with vertices ID’s and edges ID’s. This ID can be a simple integer number.

And below snippet actually gives the ‘Shortest Path’ (Pheww!)

Interesting thing is, you start from your end vertext, and keep hopping back untill you reach the start vertext.

Second thing is, Bellman Ford works on directional graphs. i.e. the edges between vertices are supposed to have direction. It’s kind of obvious right, if you have an edge having a start point and end point. Well, you end up defining a vector.

But, there are instances where we don’t have directional graphs. E.g. what if my graph is distance between cities? In that case distance between London to Paris is same distance between Paris to London.

Well in that case, you assume an edge in opposite direction with same weight for every single edge.

Third, if I calculate the graph and get the shortest path between two points. Now, user again request the shortest path between two points. Should I calculate the graph again? Why should I? haven’t I’ve already done this?

Now, you need to understand that when you calculate graph by Bellman Ford you calculated shortest distance between Source Vertex and all other vertex.

If your source vertex is different you must re-calculate your graph weights.

But, if your source vertex is same and end vertex is changing then there is no need to re-calculate the graph weights again.

Hope you find this useful!

Images taken from here.