27/01/2018

[Java] Bellman-Ford algorithm

Let's start the new year with something not overly complicated like a proven graph algorithm, Bellman-Ford.

This is a good example of an algorithm for which choosing a good data structure can be the difference between a walk in a park or in hell during implementation.
A key point here is to represent the graph a two lists: Vertices and Edges. Using a different data structure instead can lead to a very messy code and complex implementation; for example I would advise not to keep a list of out edges in each Vertex and track the out vertex in the edge itself - even though the uploaded classes allow you to do so, but I keep them for the next exercises.

Also another important point is to understand exactly how a negative cycle can be detected and tracked into the resulting data structure. While we only need (V - 1) x E iterations to create the table, we need instead VxE iterations to be absolutely sure no negative cycle exists.

Another gotcha: we use "infinity" to mark the unknown distances at the beginning, but when we update the distances themselves if we are starting from infinity it means we don't know yet how to reach that specific node, so we should skip tracking it in the table. At the end, if the node is not present in the table or the distance to the node is "infinity", it means it's unreachable.

The last important step is to remember to update the path cost to "negative infinity" for all nodes in our graph that are in a negative cycle reachable from the given starting node; this gives us a full understanding of which paths are actually valid.

You can check my implementation on my Gist along with some test cases in BellmanFordJTests. Remember to check out the Vertex and Edge classes too.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.