Implementation of Bellman-Ford Algorithm

featured
May 07, 2017
šŸ’« Originally posted here. Broken? Let me know ~

I’ve already implemented Dijkstra’s algorithm and was looking for another way to find the shortest path between two nodes in a graph.Ā I found a simpler algorithm based on relaxation called “Bellman-Ford” algorithm.

I just implemented the algorithm in C# and would like to share it.

I had many troubles implementing Dijkstra’s algorithm because I didn’t have a good understanding of how it worked. So this time, I watched more videos on the Bellman-Ford algorithm to grasp the idea behind it.

Here are the videos I found helpful.

Watch the Theory video first before diving into example video.

Theory and examples behind Bellman-Ford are very well explained in the videos and onĀ WikipediaĀ so I won’t go over them.Ā I will only show a concrete implementation in C#.Ā The implementation is based purely on algorithm listed in Wikipedia.

Wikipedia Pseudo Code

This is the pseudo code I will base my implementation.

Before showing my implementation, I need to show you the data structure of Graph and its associated classes, Node, and Edge because the declaration of the implementing method looks different from that of the pseudo code.

Here is my Graph data structure.

And Node class representing a node in a graph.

And also, my implementation of the graph has a class called “Edge” which is a line between two nodes and contains a weight and a linked node.

Actual Implementation

Here is theĀ implementing method definition.

Currently, the method GetPathInfoUsingBellmanFordAlgorithm belongs to “Graph” (I will refactor it later), which contains vertices and edges so only “sourceNode” is passed to it (thus leaving out “vertices” and “edges” parameter declarations in pseudo code).

::distance[],predecessor[] is implemented as two dictionaries as shown.

distance represents distances from source to the node being checked while predecessor holds paths between nodes.

Each step in pseudo code is implemented as following.

Step 1: initialize graph

Notice that I am initializing all vertices as well as nodes associated with each vertex because my implementation of vertices contains only vertices that have an outbound link(s) to another node.

The code is not yet optimized (since each edge can contain nodes that are already initialized) for demonstration purposes only to show 1 to 1 matching between my implementation and the Wikipedia pseudo code.

Step 2: relax edges repeatedly

In the pseudo code, there are only two for loops but the implementation has three due to the not-so-optimal data structure.

Step 3: check for negative-weight cycles

As it was the case for step 2, this implementation has additional “foreach” loop to iterate over each edge in each vertex.

Step 4: return result

Since C# doesn’t allow returning multiple values from a method, I am returning the distance and the predecessor as a tuple.Ā I will refactor it laterĀ wrapping the result in another class object.

Now the question is, how do you determine the shortest path between two nodesĀ from the return value?

Finding the shortest path

One of the return values, predecessor, contains information on how to traverse between two nodes.

Let’s use this weighted graph as an example (Example is from this YouTube video.)

 

 

 

 

 

 

 

 

The shortest path between “A” and “F” is “A->B->E->G->F”.

The predecessor returned by the method, GetPathInfoUsingBellmanFordAlgorithm looks like this.

To find the shortest path, we need to traverse from the destination back to the source node.

So when we start from 6th item(where index is 5 {[F,G]}), the value in the dictionary is “G”. Next, we look for an item where “G” is the key in the predecessor. We find that the 7th item ({[G,E]}) has “G” as the key.Ā Then iterate until we reach the source node, “A”.Ā Since we are traversing backward, it seems like a stack would do the job to return the result in LIFO order.

The implementation of a method that returns the shortest path looks like this.

After the getting the predecessor from “GetPathInfoUsingBellmanFordAlgorithm”, the code simply traverses the predecessor hash table in reverse order and stores each step in a stack.

I can’t stress enough that the code is not production ready because it’s just a demo implementation.Ā The full source is available on GitHub. You can copy it, modify it, use it, distribute it any way you want/need to.

Conclusion

I’ve described how Bellman-Ford algorithm is implemented in C#. Ā I am planning to refactor it to be more readable and structure the code properly and will push the updated code on GitHub.