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.

1

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 :

//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.

2

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.

One thought on “Bellman-Ford shortest path algorithm Tips & Tricks

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s