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.