Hello 0x00sec people! It’s @oaktree once again coming at you with another tutorial. This time, it’s about the Bellman-Ford Algorithm.
This algorithm is very similar to Dijkstra’s Algorithm from last time, yet it diverges in that it is designed to handle negative edge weights, which are “negative distances,” in a way.
The use of the algorithm is two-fold: determine the shortest path between a starting node and all other nodes in a graph; and, determine if there are any negative cycles. A negative cycle is when traversing the same path again makes the distance smaller. This would continue and approach negative infinity if we kept traversing the same negative cycle.
Applications
I’m paraphrasing Wikipedia here. This algorithm is used in the Routing Information Protocol (cough @airth). This allows each node in a network to know how far every other node is. Each node calculates the distance between it and all other reachable nodes, and then sends that information to all the other nodes, so that all the nodes can update their information if/when a shorter path is discovered.
#Procedure
Image from this guy’s wonderful Youtube video on the subject. You should all go watch that video and give him a like.
Alright: Here’s an example of a graph with negative edge weights. Our algorithm is going to go through and find the shortest distance to each node from a starting node. For this example, our starting node will be S. Once it does, it’ll go over it one more time. Any distances that get smaller will do so because of a negatively-weighted edge. When this happens, we have detected a negative cycle.
Time Complexity
To ensure that we have found the shortest path, we’ll iterate through the graph |V| - 1 times, where V is the number of vertices. Then, we’ll iterate through one last time to find the negative cycles.
All in all, the time complexity boils down to O(|V|*|E|), where E is the number of edges.
Pseudocode
bellman(start, graph, distances):
for_each vertex in graph:
distances[vertex] = infinity
distances[start] = 0
previous = Array of graph.vertex_count elements
// find the minimum distances
(graph.vertex_count - 1) times:
for_each node in graph:
for_each neighbor of node:
if distances[neighbor] > distances[node] + edge(node,neighbor):
distances[neighbor] = distances[node] + edge(node,neighbor)
previous[neighbor] = node
// go through one last time to check for negative cycles
for_each node in graph:
for_each neighbor of node:
if distances[neighbor] > distances[node] + edge(node,neighbor):
print "negative cycle found between " + node + " and " + neighbor + "\n"
As you can see, the first thing we do is set each distance to infinity. Then, we make sure that distances[start] = 0 because the distance between a node and itself should ideally be 0.
I also made an array called previous just to keep track of the path – not that it matters all that much for finding distances, though.
The next thing to do is iterate through the graph |V| - 1 times. We go through each node’s neighbors and see if we can find a better distance. If we do, we also update the previous element corresponding to the neighbor.
After all of those |V| - 1 times (it can be optimized, but I wouldn’t want to cause confusion), we loop through once more to see if there are any negative cycles. |V| - 1 times is enough iterations to determine the shortest distance, so if it’s shorter now it must be due to a negative edge weight, a negative cycle.
Conclusion
That’s about all the algorithm does. In Part 2.1 (I really like to stick with my conventions), we’ll write out some C++ code to perform the algorithm.
Graph ya’ later,
@oaktree
P.S. If you have Sublime Text 2/3, get the DarkKorokai color scheme.