A very interesting application of the bellman-ford algorithm is arbitrage, essentially, given a table of currencies and their exchange rates, one needs to be able to figure out if we can start with a certain amount of money in one currency, exchange this amount for other currencies and end up with more money than what we had at first.

Example: 1 USD gives us 0.8 Euro and 1 Euro gives us 0.8 GBP and 1 GBP gives us 1.7 USD. So if I start with 1 dollar, I can exchange it for 0.8 Euro which can then be exchanged for 0.64 GBP and if converted back to USD we have 1.088 dollars.

So if rate_i_j is used to represent the amount of currency_j which we can get for 1 unit of currency_i, we observe:

rate_i_j * rate_j_k * rate_k_l * ..... * rate_z_i > 1

Invert this to get:

1/(rate_i_j * rate_j_k * rate_k_l * ..... * rate_z_i) < 1

and take lg on both sides:

lg(1/rate_i_j) + lg(1/rate_j_k) + ..... + lg(1/rate_z_i) < 0

So we observe that if we represent our table using a graph with lg(1/exchange_rate) as the weights, then the presence of a negative weight cycle is all that is needed to ensure we get more $$ than we started out with.

And of course, negative weight cycle detection is really easy with the bellman-ford single source shortest path algorithm.

This algorithm operates by the following dynamic programming equation:

distanceFromSource(v) = distanceFromSource(w) + weight(w, v)

When we set the distance of vertex 'v' from the source, we look at the edge (w, v) and observe that if we can get to 'v' by a shorter path through 'w', we discard the old distance and set distanceFromSource(w) + weight(w, v) as the new distance. This operation is called "Relaxing an edge"

Now, we only need to observe every edge a certain number of times. Precisely |V| - 1 times. Why? Well, consider a graph where the max out-degree is 1.

So, we have something like: v1 ----> v2 -----> v3 -----> v4 ------> ........ ------> v{n}. This is a directed graph with n vertices. If our source is v1, in the first of |V| - 1 iterations, we relax the first edge and fix the path to v2 (cannot get to v2 using a shorter path see?). In the second iteration, the path to v3 is fixed and continuing this we finish fixing the paths to the vertices |V| - 1 iterations (Remember, you relax **every** edge in each iteration).

To detect a negative weight cycle, finish relaxing all the edges |V| - 1 times. Now, carry the relax operation out once again. Since, all paths from the source to each vertex are guaranteed to be fixed by now, if you ever stumble upon a situation where you change distanceFromSource(v) for a vertex v, then a negative weight cycle starts and ends at v. The result of this is that a shortest path to v cannot be found, since for every path to v, you can make another trip about this negative-weight cycle and obtain an even shorter path.

So, I wrote a simple script for the Bellman-Ford routine and tested it using the USD, Euro, GBP example.

Here's the Bellman-Ford routine:

```
#!/usr/bin/env python
#Author: Shriphani Palakodety
#Bellman Ford Implementation. Look it up on wikipedia.
distances = {}
parents = {}
def Initialize(graph, start):
'''Prepares the graph for the bellman-ford algorithm'''
for vertex in graph.V:
if graph.E.has_key((start, vertex)):
distances[vertex] = 9999999e6
distances[start] = 0
parents[start] = None
def Bellman_Ford(graph, start):
Initialize(graph, start) #first initialize the graph
for i in xrange(len(graph.V) - 1):
for edge in graph.E.keys():
if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
distances[edge[1]] = graph.E[edge] + distances[edge[0]]
parents[edge[1]] = edge[0]
#one final check for negative weight cycles.
for edge in graph.E.keys():
if (graph.E[edge] + distances[edge[0]]) < distances[edge[1]]:
distances[edge[1]] = graph.E[edge] + distances[edge[0]]
parents[edge[1]] = edge[0]
return edge[1] #return here since, a negative weight cycle is detected
return None #return none on successful completion.
```

And the test itself:

```
!/usr/bin/env python
#Author: Shriphani Palakodety
#Mail: spalakod@purdue.edu
#Testing Arbitrage
#import graph
import bellman_ford
from math import log
#in the format cur1_cur2 = no. of units of cur2 for 1 unit of cur1
usd_euro = 0.8
euro_gbp = 0.8
gbp_usd = 1.7
#Nodes List
nodes = ["usd", "euro", "gbp"]
edge_dict = { ("usd", "euro") : log(1/usd_euro), ("euro", "gbp") : log(1/euro_gbp), ("gbp", "usd") : log(1/gbp_usd), ("euro", "usd") : log(usd_euro), ("gbp", "euro") : log(euro_gbp), ("usd", "gbp") : log(gbp_usd)}
#make a small graph to represent the currency network.
cur_graph = bellman_ford.Graph(nodes, edge_dict)
print bellman_ford.Bellman_Ford(cur_graph, "usd")
```

And when run, I get:

?(shriphani@Shriphani-Palakodetys-MacBook-Pro)?(533/ttys001)?(09:10P:07/02/10)?- ??(%:~/scripts)?- python arbitrage_test.py usd ??(shriphani@Shriphani-Palakodetys-MacBook-Pro)?(534/ttys001)?(09:10P:07/02/10)?- ??(%:~/scripts)?-

So, there's a negative weight cycle and if you kick off with some USD, you can get rich.

Get my routines here:

My code reads too much like pseudocode. Didn't know a theory class corrupts so much.

[...] This post was mentioned on Twitter by hiu , Planet Python. Planet Python said: Shriphani Palakodety: Bellman-Ford Algorithm’s Applications – Triangular Arbitrage http://bit.ly/8XJt3R [...]

Great job.

This is useless. Simple triangular arbitrage never occurs in real life. And this is a very useless problem in itself.

As someone implements systems that take advantage of triangular arbitrage in the spot forex I beg to differ. It occurs very,very frequently in real life but the returns are tiny after transaction costs, their duration often milliseconds and you have to have some serious hardware to exploit them after detection.

Look for a 2009 paper by Daniel Fenn "The Mirage of Triangular Arbitrage in the spot foreign exchange market"

Thanks a lot for that information!

I guess relying on a computing textbook to impart knowledge of the financial world is wrong

can u please give me little information about bellmanford algorithm??

i'm in need of it i just want to know that in finding shortest path using bellmanford algorithm... can we choose the destination node...?? i mean will there be a destination node in this algorithm??

Looking at the algorithm should give you some intuition. Essentially the way you see it is, we relax edges |V - 1| times. Basically, every iteration should fix the shortest path to one vertex in this graph. When we approach V-1 iterations, we should have resolved the shortest paths to all V vertices. For a destination node either:

1. Terminate when you fix the shortest path to this node in some iteration (see CLRS for what fixing/relaxing etc mean).

2. Allow the algorithm to terminate, you should have a map from vertices to their distance from the source. Use that.

Hope this helps.

Hi there just wanted to give you a quick heads up.

The text in your post seem to be running off the screen in Firefox.

I'm not sure if this is a format issue or something to do with internet browser compatibility but I thought I'd post to let you know.

The design and style look great though! Hope you get

the issue resolved soon. Cheers