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.

- Calculating the graph weights
- 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 :

//Have dictionary for keeping track of list of nodes visited Dictionary<int, int> vertexTrail; //Initialize for all edge previous edge is equal to INT_MIN value //Also understand that, number of entries in this dictionary is equal to number of edges in graph. for (/*run though list of all edges*/) { vertexTrail.Add(edgeID, INT_MIN); } //if the relaxation condition is met if ((vertexWeights[startVertexID] + curEdgeLength) < vertexWeights[endVertexID]) { //update vertex weights vertexWeights[endVertexID] = vertexWeights[startVertexID] + curEdgeLength; //and also keep track of trail! //i.e. for this end vertex the previous vertex is the start vertex. which is the shortest path vertexTrail[endVertexID] = startVertexID; }

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!)

// endVertex : end vertex from which you want to find out shortest path (till the start vertex) // Dictionary<int, int> vertexTrail : trail of vertices calculated in previous step // List<int> shortestPathEdges : list of shortest path edge IDs int GetShortestPath(int endVertex, Dictionary<int, int> vertexTrail, List<int> shortestPathEdges) { int resultCode = -1; // unknown error. int currentVertexID = endVertex; if (vertexTrail.ContainsKey(currentVertexID)) { int prevVertexID = vertexTrail[currentVertexID]; //when you reach the start vertex, this loop will exit while (prevVertexID != INT_MIN) { int edgeID = GetEdgeBetweenVertices(prevVertexID, currentVertexID); if (edgeID != null) { pShortestPathEdges.add(edgeID); resultCode = 0; } else { resultCode = -2; // Path not found break; } //hop one step back. Now, your previous Vertex is current Vetext. And find it's previous vertex now. currentVertexID = prevVertexID; prevVertexID = vertexTrail[currentVertexID]; } } else { // Path not found resultCode = -2; } //list is populated from end to start. reverse it. pShortestPathEdges.reverse(); return resultCode; }

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.

[…] For first part check this. […]

LikeLike