The Belleman-Ford Algorithm

Okay, so the longer I write these out the more difficult they become to explain because the concepts sorta get more dense and I don’t want to write out a 10 page paper explaining everything. The astute among you might note that this probably means this isn’t a good topic to share in this format and it would make more sense for me to do something else, but I’m not smart enough to quit while I’m still ahead. So, onward we march.

Hopefully, if you’ve read my past two blogs, you have a general understanding of what arbitrage is and what mathematical graphs are. We’re going to build on those concepts today with an algorithm that uses graphical representations of currency exchange to find arbitrage: the Bellman-Ford algorithm.

This algorithm is designed to find the shortest path between a series of nodes with negative edge weights. We can demonstrate this pictorially with a fun new graph:

Looking at this graph there is a lot going on, but the important takeaways are that each edge between nodes has a direction and a weight. This means that I can now only travel from one node to another if there is an arrow pointing from my starting node to my ending node and when I traveled it would take me a given amount of time to reach the other node. For example, I could travel from node A to C in two minutes, but I could not travel back to A from C directly.

The Bellman-Ford Algorithm is used to find the shortest path between an arbitrary starting node and each other node in the graph, and it operates like this.

1) Begin by picking an arbitrary starting node and assuming that the distance to each other node is infinity.

For our example, A is the starting node and the current distances to each other node are highlighted in green.

2) Begin evaluating each edge leading out from A and relaxing the distance to the connected nodes if they are inaccurate.

Now we have more realistic distances to B and C based on the edge weights from A.

3) Now we look at the edges going out from B and change the distances to the connected nodes to the weight of the connecting edge plus the distance to B. Obviously, we only want to change the distance if it’s shorter than the current distance.

D now has a distance from A of 8 because the distance from A to B is 5 and the distance from B to D is 3 (This will change as we find shorter paths to D). A’s distance did not change because 0 is less than the distance from B to A (which also happens to be 3).

4) Now we do the same thing we did with B, except this time with node C

This time D’s distance to A changed from 8 to 7 because we found a shorter path through C, and E got a new value of 4.

5) This time we’re going to look at the edges going out from E (instead of D like you might have expected) because it has a shorter distance than D [1].

D’s value has changed yet again because we found another shorter path through C then E than just through C.

6) Now we will come back to looking at the nodes leaving D and reassigning the distances from there.

The edge leaving D has a negative weight so we subtract its value from the distance between A and D and find that we can get a distance from A to C that is zero by looping through D’s negative edge weight.

This doesn’t really need to make sense in the context of traveling between nodes in terms of distance or time, because what we’re really interested in is money. If we think about each jump as a cost incurred to get from one node to another and the negative weighted edge as a payout, then we have found a way to make (theoretically) infinite money by looping through the negative weight cycle as many times as we can. This is what arbitrage is within forex markets and finding these opportunities on graphs that are significantly larger than this one is the point of the Belleman-Ford Algorithm [2].

I hope that all of this made some kind of sense, or at least the pictures were interesting to look at. Next week I’ll show a fun code demonstration of this algorithm and some others (might do overviews of other algorithms at some point in the near future too) and get into more clear examples of how this can be applied to forex graph representations instead of the strange abstraction we worked with today. Have a nice day.
[1] – And because it helps me avoid some of the nuances of the algorithm that wouldn’t really help construct the understanding of what’s going on here. Sorry if this seems arbitrary.

[2] – We didn’t really go through all the steps of the algorithm, I stopped when it seemed like my point was demonstrated. You don’t need to have a fully developed understanding of each minute step to get what it does.